localSources method

List<Set<T>>? localSources()
inherited

Returns a list of type List<Set<T>> if the graph is acyclic or null otherwise.

  • The first entry contains the source vertices of the graph, that is vertices with no inbound edges. Any acyclic graph must have at least one source vertex.

  • 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<Set<T>>? localSources() {
  final result = <Set<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;
}