Class StronglyConnectedComponents

java.lang.Object
com.phasmidsoftware.gryphon.java.StronglyConnectedComponents

public class StronglyConnectedComponents extends Object
Java façade for strongly-connected-components analysis on directed graphs, using Kosaraju's two-pass algorithm.

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 Details

    • kosaraju

      public static <V> Map<V,Integer> kosaraju(Graph<V> graph)
      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 - if graph is undirected.
    • count

      public static <V> int count(Graph<V> graph)
      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 - if graph is undirected.
    • components

      public static <V> Map<Integer,Set<V>> components(Graph<V> graph)
      Returns the vertices grouped by SCC as a Map<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 - if graph is undirected.