localSources property
Returns a list of type List<List<T>>
.
The first entry contains the
local source vertices of the graph.
Subsequent entries contain the local source vertices of the reduced graph.
The reduced graph is obtained by removing all vertices listed in
previous entries from the original graph.
Note: Concatenating the entries of localSources
in sequential order
results in a topological ordering of the graph vertices.
Note: There is no topological ordering if the
graph is cyclic. In that case the function returns null
.
Implementation
List<List<T>>? get localSources {
final result = <List<T>>[];
final vertices = LinkedHashSet<T>.of(sortedVertices);
final localInDegreeMap = Map<T, int>.of(inDegreeMap);
var hasSources = false;
var count = 0;
// Note: In an acyclic directed graph at least one
// vertex has outDegree zero.
do {
// Storing local sources.
final sources = <T>[];
// Find local sources.
for (final vertex in vertices) {
if (localInDegreeMap[vertex] == 0) {
sources.add(vertex);
++count;
}
}
// Add sources to result:
if (sources.isNotEmpty) result.add(sources);
// Simulate the removal of detected local sources.
for (final source in sources) {
for (final connectedVertex in edges(source)) {
var inDegree = localInDegreeMap[connectedVertex]!;
inDegree--;
localInDegreeMap[connectedVertex] = inDegree;
}
}
// Check if local sources were found.
hasSources = sources.isNotEmpty;
vertices.removeAll(sources);
} while (hasSources);
return (count == length) ? result : null;
}