edu.uci.ics.jung.algorithms.cluster

Class BicomponentClusterer<V,E>

java.lang.Object

edu.uci.ics.jung.algorithms.cluster.BicomponentClusterer<V,E>

All Implemented Interfaces:

com.google.common.base.Function<UndirectedGraph<V,E>,java.util.Set<java.util.Set<V>>>

public class BicomponentClusterer<V,E>
extends java.lang.Object
implements com.google.common.base.Function<UndirectedGraph<V,E>,java.util.Set<java.util.Set<V>>>

Finds all biconnected components (bicomponents) of an undirected graph. A graph is a biconnected component if at least 2 vertices must be removed in order to disconnect the graph. (Graphs consisting of one vertex, or of two connected vertices, are also biconnected.) Biconnected components of three or more vertices have the property that every pair of vertices in the component are connected by two or more vertex-disjoint paths.

Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges

See Also:

"Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."

Constructor Summary

Constructors

Constructor and Description
BicomponentClusterer() Constructs a new bicomponent finder

Method Summary

Modifier and Type	Method and Description
java.util.Set<java.util.Set<V>>	apply(UndirectedGraph<V,E> theGraph) Extracts the bicomponents from the graph.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.google.common.base.Function

equals

Constructor Detail

BicomponentClusterer

public BicomponentClusterer()

Constructs a new bicomponent finder

Method Detail

apply

public java.util.Set<java.util.Set<V>> apply(UndirectedGraph<V,E> theGraph)

Extracts the bicomponents from the graph.

Specified by:

apply in interface com.google.common.base.Function<UndirectedGraph<V,E>,java.util.Set<java.util.Set<V>>>

Parameters:

theGraph - the graph whose bicomponents are to be extracted

Returns:

the ClusterSet of bicomponents