stronglyConnected<T> function Graphs

List<List<T>> stronglyConnected<T>(
  1. WalkableBase<T> graph, {
  2. Iterable<T>? from,
  3. Tracer<T>? tracer,
})

Partitions nodes reachable in a graph into strongly connected components.

A strongly connected component is a subset of a graph where every node is reachable from every other node in the subset. The function returns a list of strongly connected component sets, containing at last one component (the ones containing from, if provided, otherwise all root nodes).

Example

final graph = Graph<int>();

graph.addEdge(Edge(1, 2));
graph.addEdge(Edge(2, 3));
graph.addEdge(Edge(3, 2));

final components = stronglyConnected(graph, start: 1);
print(components); // [[2, 3], [1]]

Implementation

List<List<T>> stronglyConnected<T>(
  WalkableBase<T> graph, {
  Iterable<T>? from,
  Tracer<T>? tracer,
}) {
  final context = _StronglyConnectedContext<T>(graph.asUnweighted(), tracer);
  from ??= graph.roots;
  for (final root in from) {
    context.preorders[root] = null;
  }
  for (final root in from) {
    context.recurse(root);
  }
  return context.scc;
}