localSources property

List<List<T>>? localSources
inherited

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;
}