|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object nz.ac.waikato.mcennis.rat.graph.model.ModelShell nz.ac.waikato.mcennis.rat.graph.algorithm.clustering.BicomponentClusterer
public class BicomponentClusterer
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
Field Summary | |
---|---|
protected int |
converse_depth
|
protected java.util.Map<Actor,java.lang.Number> |
dfs_num
|
protected int |
graphCount
|
protected java.util.Map<Actor,java.lang.Number> |
high
|
protected java.util.Map<Actor,Actor> |
parents
|
protected java.util.Stack<Link> |
stack
|
Fields inherited from class nz.ac.waikato.mcennis.rat.graph.model.ModelShell |
---|
listener |
Constructor Summary | |
---|---|
BicomponentClusterer()
|
Method Summary | |
---|---|
void |
execute(Graph g)
execute the algorithm against the given graph |
protected void |
findBiconnectedComponents(Graph g,
Actor v,
java.util.Set<java.util.Set<Actor>> bicomponents)
Stores, in bicomponents , all the biconnected
components that are reachable from v . |
InputDescriptor[] |
getInputType()
The input type describes all the different kinds of graph objects that are utilized (and hence required) by this object. |
protected Link[] |
getLinks(Graph g,
Actor v)
|
protected Actor |
getOther(Link l,
Actor a)
|
OutputDescriptor[] |
getOutputType()
The output type describes all the different kinds of graph objects that are created during the execution of this algorithm. |
Parameter[] |
getParameter()
List of all parameters this component accepts. |
Parameter |
getParameter(java.lang.String param)
Returns the specific parameter identified by its key-name. |
SettableParameter[] |
getSettableParameter()
Returns settable (i.e. |
SettableParameter |
getSettableParameter(java.lang.String param)
Return the settable parameter namede by this key-name. |
void |
init(java.util.Properties map)
Parameters to be initialized. |
Methods inherited from class nz.ac.waikato.mcennis.rat.graph.model.ModelShell |
---|
addListener, fireChange |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Methods inherited from interface nz.ac.waikato.mcennis.rat.graph.model.Model |
---|
addListener |
Field Detail |
---|
protected java.util.Map<Actor,java.lang.Number> dfs_num
protected java.util.Map<Actor,java.lang.Number> high
protected java.util.Map<Actor,Actor> parents
protected java.util.Stack<Link> stack
protected int converse_depth
protected int graphCount
Constructor Detail |
---|
public BicomponentClusterer()
Method Detail |
---|
public void execute(Graph g)
Algorithm
execute
in interface Algorithm
g
- graph to be modifiedpublic InputDescriptor[] getInputType()
Component
getInputType
in interface Component
InputDescriptor
public OutputDescriptor[] getOutputType()
Component
getOutputType
in interface Component
OutputDescriptor
public Parameter[] getParameter()
Component
getParameter
in interface Component
public Parameter getParameter(java.lang.String param)
Component
getParameter
in interface Component
param
- key-name of the parameter
public SettableParameter[] getSettableParameter()
Component
getSettableParameter
in interface Component
public SettableParameter getSettableParameter(java.lang.String param)
Component
getSettableParameter
in interface Component
param
- key-name of the parameter
public void init(java.util.Properties map)
init
in interface Component
map
- map of the given properties naming parameters and their values in a stringprotected void findBiconnectedComponents(Graph g, Actor v, java.util.Set<java.util.Set<Actor>> 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 Link[] getLinks(Graph g, Actor v)
protected Actor getOther(Link l, Actor a)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |