public class BicomponentClusterer extends java.lang.Object implements GraphClusterer
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 java.util.Map |
dfs_num |
protected java.util.Map |
high |
protected java.util.Map |
parents |
protected java.util.Stack |
stack |
Constructor and Description |
---|
BicomponentClusterer()
Constructs a new bicomponent finder
|
Modifier and Type | Method and Description |
---|---|
ClusterSet |
extract(ArchetypeGraph theGraph)
Extracts the bicomponents from the graph
|
protected void |
findBiconnectedComponents(Vertex v,
ClusterSet bicomponents)
Stores, in
bicomponents , all the biconnected
components that are reachable from v . |
protected int |
get(Vertex v,
java.util.Map m)
A convenience method for getting the integer value for
v which is stored in Map m . |
protected void |
set(Vertex v,
java.util.Map m,
int value)
A convenience method for setting an integer value
for
v in Map m . |
protected java.util.Map dfs_num
protected java.util.Map high
protected java.util.Map parents
protected java.util.Stack stack
protected int converse_depth
public BicomponentClusterer()
public ClusterSet extract(ArchetypeGraph theGraph)
extract
in interface GraphClusterer
theGraph
- the graph whose bicomponents are to be extractedClusterSet
of bicomponentsprotected void findBiconnectedComponents(Vertex v, ClusterSet 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)
protected int get(Vertex v, java.util.Map m)
v
which is stored in Map m
.
Does no error checking.protected void set(Vertex v, java.util.Map m, int value)
v
in Map m
.