public class BicomponentClusterer<V,E> extends Object implements com.google.common.base.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
Modifier and Type | Field and Description |
---|---|
protected int |
converse_depth |
protected Map<V,Number> |
dfs_num |
protected Map<V,Number> |
high |
protected Map<V,V> |
parents |
protected Stack<E> |
stack |
Constructor and Description |
---|
BicomponentClusterer()
Constructs a new bicomponent finder
|
Modifier and Type | Method and Description |
---|---|
Set<Set<V>> |
apply(UndirectedGraph<V,E> theGraph)
Extracts the bicomponents from the graph.
|
protected void |
findBiconnectedComponents(UndirectedGraph<V,E> g,
V v,
Set<Set<V>> bicomponents)
Stores, in
bicomponents , all the biconnected
components that are reachable from v . |
public BicomponentClusterer()
public Set<Set<V>> apply(UndirectedGraph<V,E> theGraph)
protected void findBiconnectedComponents(UndirectedGraph<V,E> g, V v, Set<Set<V>> bicomponents)
Stores, in bicomponents
, all the biconnected
components that are reachable from v
.
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)
g
- the graph to check for biconnected componentsv
- the starting place for searching for biconnected componentsbicomponents
- storage for the biconnected components found by this algorithmCopyright © 2015. All rights reserved.