localSources property

List<List<Vertex<T>>> localSources

Returns a list of type List<List<Vertex<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<Vertex<T>>> get localSources {
  final result = <List<Vertex<T>>>[];

  // Get modifiable in-degree map.
  final _inDegreeMap = inDegreeMap;

  // Get modifiable list of the graph vertices
  final _vertices = List.from(vertices);

  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 = <Vertex<T>>[];

    // Storing remaining vertices.
    final remainingVertices = <Vertex<T>>[];

    // Find local sources.
    for (final vertex in _vertices) {
      if (_inDegreeMap[vertex] == 0) {
        sources.add(vertex);
        ++count;
      } else {
        remainingVertices.add(vertex);
      }
    }

    // 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] ?? []) {
        _inDegreeMap[connectedVertex] -= 1;
      }
    }
    // Check if local source were found.
    hasSources = sources.isNotEmpty;

    // Replacing vertices with remaining vertices.
    _vertices.clear();
    _vertices.addAll(remainingVertices);
  } while (hasSources);

  return (count == inDegreeMap.keys.length) ? result : null;
}