sortedTopologicalOrdering property
Returns an ordered set of all vertices in topological order.
-
For every directed edge: (vertex1 -> vertex2), vertex1 is listed before vertex2.
-
If a vertex comparator is specified, the sorting will be applied in addition to the topological order.
-
Note: There is no topological ordering if the graph is cyclic. In that case the function returns
null
. -
Any self-loop renders a directed graph cyclic.
-
Based on Kahn's algorithm.
Implementation
Set<T>? get sortedTopologicalOrdering {
if (_comparator == null) return topologicalOrdering;
final result = Queue<T>();
int inverseComparator(T left, T right) => -_comparator!(left, right);
// Get modifiable in-degree map.
final localInDegreeMap = inDegreeMap;
// Add all sources (vertices with inDegree == 0) to queue.
// Using a list instead of a queue to enable sorting of [sources].
//
// Note: In an acyclic directed graph there is at least
// one vertex with inDegree equal to zero.
final sources = <T>[];
for (final vertex in sortedVertices) {
if (localInDegreeMap[vertex] == 0) {
sources.add(vertex);
}
}
// Initialize count of visited vertices.
var count = 0;
// Note: In an acyclic directed graph at least
// one vertex has outDegree zero.
while (sources.isNotEmpty) {
// Sort source vertices:
sources.sort(inverseComparator);
result.add(sources.removeLast());
// Simulate removing the current vertex from the
// graph. => Connected vertices will have inDegree = inDegree - 1.
for (final vertex in edges(result.last)) {
localInDegreeMap[vertex] = localInDegreeMap[vertex]! - 1;
// Add new local source vertices of the remaining graph to the queue.
if (localInDegreeMap[vertex] == 0) {
sources.add(vertex);
}
}
// Increment count of visited vertices.
count++;
}
return (count != length) ? null : result.toSet();
}