Class ConnectedComponents

java.lang.Object
com.phasmidsoftware.gryphon.java.ConnectedComponents

public class ConnectedComponents extends Object
Java façade for connected-components analysis on undirected graphs.

A connected component is a maximal set of vertices such that there is a path between every pair of vertices in the set.

The graph must be undirected. Calling these methods on a directed graph will throw IllegalStateException.

Usage example:


 Graph<String> g = Graph.undirected();
 g.addEdge("A", "B");
 g.addEdge("C", "D");  // separate component

 int n = ConnectedComponents.count(g);          // 2
 Map<String, Integer> ids = ConnectedComponents.componentIds(g);
 ids.get("A") == ids.get("B")  // true
 ids.get("A") == ids.get("C")  // false

 Map<Integer, Set<String>> groups = ConnectedComponents.components(g);
 // groups: {0 -> {A, B}, 1 -> {C, D}}
 
  • Method Details

    • count

      public static <V> int count(Graph<V> graph)
      Returns the number of connected components in the graph.
      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - an undirected graph.
      Returns:
      the number of connected components.
      Throws:
      IllegalStateException - if graph is directed.
    • componentIds

      public static <V> Map<V,Integer> componentIds(Graph<V> graph)
      Returns a map from each vertex to its integer component id.

      Vertices with the same id belong to the same connected component. Component ids are assigned in DFS discovery order starting from 0.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - an undirected graph.
      Returns:
      an unmodifiable Map<V, Integer> mapping vertex to component id.
      Throws:
      IllegalStateException - if graph is directed.
    • components

      public static <V> Map<Integer,Set<V>> components(Graph<V> graph)
      Returns the vertices grouped by component as a Map<Integer, Set<V>>.
      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - an undirected graph.
      Returns:
      an unmodifiable map from component id to the set of vertices in that component.
      Throws:
      IllegalStateException - if graph is directed.