Class StronglyConnectedComponents
A strongly connected component (SCC) is a maximal set of vertices such that there is a directed path from every vertex in the set to every other. Kosaraju's algorithm finds all SCCs in O(V + E) time.
The result is a Map<V, Integer> mapping each vertex to an integer
SCC identifier. Vertices that share the same id belong to the same SCC.
SCC ids are assigned in topological order of the condensation DAG — the SCC
with the smallest id is a "source" component (no incoming cross-edges from
other SCCs).
The graph must be directed. Calling these methods on an undirected graph
will throw IllegalStateException.
Usage example:
Graph<String> g = Graph.directed();
g.addEdge("A", "B");
g.addEdge("B", "C");
g.addEdge("C", "A"); // cycle: A, B, C form one SCC
g.addEdge("C", "D"); // D is a singleton SCC
Map<String, Integer> sccs = StronglyConnectedComponents.kosaraju(g);
sccs.get("A") == sccs.get("B") // true — same SCC
sccs.get("A") == sccs.get("D") // false — different SCCs
// Count SCCs
long count = sccs.values().stream().distinct().count(); // 2
// Group vertices by SCC
Map<Integer, List<String>> groups = new HashMap<>();
sccs.forEach((v, id) ->
groups.computeIfAbsent(id, k -> new ArrayList<>()).add(v));
-
Method Summary
Modifier and TypeMethodDescriptioncomponents(Graph<V> graph) Returns the vertices grouped by SCC as aMap<Integer, Set<V>>.static <V> intReturns the number of strongly connected components in the graph.Computes the strongly connected components of a directed graph using Kosaraju's algorithm.
-
Method Details
-
kosaraju
Computes the strongly connected components of a directed graph using Kosaraju's algorithm.The graph may have unweighted edges (plain
Edge<V>) or weighted edges (WeightedEdge<V, E>) — edge weights are ignored for SCC computation.- Type Parameters:
V- the vertex type.- Parameters:
graph- a directed graph.- Returns:
- a
Map<V, Integer>mapping each vertex to its SCC id; vertices with the same id are in the same SCC. - Throws:
IllegalStateException- ifgraphis undirected.
-
count
Returns the number of strongly connected components in the graph.Convenience method — equivalent to
kosaraju(graph).values().stream().distinct().count().- Type Parameters:
V- the vertex type.- Parameters:
graph- a directed graph.- Returns:
- the number of SCCs.
- Throws:
IllegalStateException- ifgraphis undirected.
-
components
Returns the vertices grouped by SCC as aMap<Integer, Set<V>>.Convenience method for when the full grouping is needed rather than per-vertex lookup.
- Type Parameters:
V- the vertex type.- Parameters:
graph- a directed graph.- Returns:
- a map from SCC id to the set of vertices in that component.
- Throws:
IllegalStateException- ifgraphis undirected.
-