Class BicomponentClusterer<V,E>
- All Implemented Interfaces:
com.google.common.base.Function<UndirectedGraph<V,
,E>, Set<Set<V>>> Function<UndirectedGraph<V,
E>, Set<Set<V>>>
Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges
- See Also:
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionapply
(UndirectedGraph<V, E> theGraph) Extracts the bicomponents from the graph.protected void
findBiconnectedComponents
(UndirectedGraph<V, E> g, V v, Set<Set<V>> bicomponents) Stores, inbicomponents
, all the biconnected components that are reachable fromv
.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface com.google.common.base.Function
equals
-
Field Details
-
dfs_num
-
high
-
parents
-
stack
-
converse_depth
protected int converse_depth
-
-
Constructor Details
-
BicomponentClusterer
public BicomponentClusterer()Constructs a new bicomponent finder
-
-
Method Details
-
apply
Extracts the bicomponents from the graph. -
findBiconnectedComponents
Stores, in
bicomponents
, all the biconnected components that are reachable fromv
.The algorithm basically proceeds as follows: do a depth-first traversal starting from
v
, marking each vertex with a value that indicates the order in which it was encountered (dfs_num), and with a value that indicates the highest point in the DFS tree that is known to be reachable from this vertex using non-DFS edges (high). (Since it is measured on non-DFS edges, "high" tells you how far back in the DFS tree you can reach by two distinct paths, hence biconnectivity.) Each time a new vertex w is encountered, push the edge just traversed on a stack, and call this method recursively. If w.high is no greater than v.dfs_num, then the contents of the stack down to (v,w) is a biconnected component (and v is an articulation point, that is, a component boundary). In either case, set v.high to max(v.high, w.high), and continue. If w has already been encountered but is not v's parent, set v.high max(v.high, w.dfs_num) and continue.(In case anyone cares, the version of this algorithm on p. 224 of Udi Manber's "Introduction to Algorithms: A Creative Approach" seems to be wrong: the stack should be initialized outside this method, (v,w) should only be put on the stack if w hasn't been seen already, and there's no real benefit to putting v on the stack separately: just check for (v,w) on the stack rather than v. Had I known this, I could have saved myself a few days. JRTOM)
- Parameters:
g
- the graph to check for biconnected componentsv
- the starting place for searching for biconnected componentsbicomponents
- storage for the biconnected components found by this algorithm
-