Package com.phasmidsoftware.gryphon.java
Class ConnectedComponents
java.lang.Object
com.phasmidsoftware.gryphon.java.ConnectedComponents
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 Summary
Modifier and TypeMethodDescriptioncomponentIds(Graph<V> graph) Returns a map from each vertex to its integer component id.components(Graph<V> graph) Returns the vertices grouped by component as aMap<Integer, Set<V>>.static <V> intReturns the number of connected components in the graph.
-
Method Details
-
count
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- ifgraphis directed.
-
componentIds
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- ifgraphis directed.
-
components
Returns the vertices grouped by component as aMap<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- ifgraphis directed.
-