stronglyConnectedComponents property

List<List<T>> stronglyConnectedComponents
inherited

Returns a list of strongly connected components.

  • If vertices a and b belong to the same strongly connected component, then vertex a is reachable from b and vertex b is reachable from a.
  • Uses Tarjans algorithm: (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#References)
  • If a graph is acyclic, each strongly connected component consists of a single vertex and the vertices are listed in inverse topological order.(The reverse is only true if the graph does not contains any self-loops, that is edges pointing from a vertex to itself.)

Implementation

List<List<T>> get stronglyConnectedComponents {
  final queue = Queue<T>();
  var index = 0;
  final result = <List<T>>[];

  final lowLink = HashMap<T, int>();
  final indices = HashMap<T, int>();

  void strongConnect(T vertex) {
    lowLink[vertex] = index;
    indices[vertex] = index;
    index++;
    queue.addLast(vertex);

    for (final connectedVertex in edges(vertex)) {
      if (!indices.containsKey(connectedVertex)) {
        strongConnect(connectedVertex);
        lowLink[vertex] = min(lowLink[vertex]!, lowLink[connectedVertex]!);
      } else if (queue.contains(connectedVertex)) {
        lowLink[vertex] = min(lowLink[vertex]!, indices[connectedVertex]!);
      }
    }

    // Check if vertex is a root node:
    if (lowLink[vertex] == indices[vertex]) {
      final scc = <T>[];
      late T componentVertex;
      do {
        componentVertex = queue.removeLast();
        scc.add(componentVertex);
      } while (vertex != componentVertex);
      result.add(scc);
    }
  }

  for (final vertex in sortedVertices) {
    if (!indices.containsKey(vertex)) {
      strongConnect(vertex);
    }
  }
  return result;
}