nz.ac.waikato.mcennis.rat.graph.algorithm.clustering
Class BicomponentClusterer

java.lang.Object
  extended by nz.ac.waikato.mcennis.rat.graph.model.ModelShell
      extended by nz.ac.waikato.mcennis.rat.graph.algorithm.clustering.BicomponentClusterer
All Implemented Interfaces:
java.io.Serializable, Component, Algorithm, Model

public class BicomponentClusterer
extends ModelShell
implements Algorithm

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.", Serialized Form

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

dfs_num

protected java.util.Map<Actor,java.lang.Number> dfs_num

high

protected java.util.Map<Actor,java.lang.Number> high

parents

protected java.util.Map<Actor,Actor> parents

stack

protected java.util.Stack<Link> stack

converse_depth

protected int converse_depth

graphCount

protected int graphCount
Constructor Detail

BicomponentClusterer

public BicomponentClusterer()
Method Detail

execute

public void execute(Graph g)
Description copied from interface: Algorithm
execute the algorithm against the given graph

Specified by:
execute in interface Algorithm
Parameters:
g - graph to be modified

getInputType

public InputDescriptor[] getInputType()
Description copied from interface: Component
The input type describes all the different kinds of graph objects that are utilized (and hence required) by this object. This result is only guaranteed to be fixed if structural parameters are not modified. This is an empty array if there is no input.

Specified by:
getInputType in interface Component
Returns:
InputDescriptor array for this component
See Also:
InputDescriptor

getOutputType

public OutputDescriptor[] getOutputType()
Description copied from interface: Component
The output type describes all the different kinds of graph objects that are created during the execution of this algorithm. The result is only guaranteed to be fixed if structural parameters are not modified. This is an empty array if there is no output.

Specified by:
getOutputType in interface Component
Returns:
OutputDescriptor array for this component
See Also:
OutputDescriptor

getParameter

public Parameter[] getParameter()
Description copied from interface: Component
List of all parameters this component accepts. Each parameter also has a distinct key-name used when initializing the object using the init method. If there are no parameters, null is returned.

Specified by:
getParameter in interface Component
Returns:
read-only array of Parameters

getParameter

public Parameter getParameter(java.lang.String param)
Description copied from interface: Component
Returns the specific parameter identified by its key-name. If no parameter is found with this key-name, null is returned.

Specified by:
getParameter in interface Component
Parameters:
param - key-name of the parameter
Returns:
named parameter

getSettableParameter

public SettableParameter[] getSettableParameter()
Description copied from interface: Component
Returns settable (i.e. editable while running) parameters. If none exist, null is returned.

Specified by:
getSettableParameter in interface Component
Returns:
array of settable parameters

getSettableParameter

public SettableParameter getSettableParameter(java.lang.String param)
Description copied from interface: Component
Return the settable parameter namede by this key-name. If this parameter is not found or is not settable, null is returned.

Specified by:
getSettableParameter in interface Component
Parameters:
param - key-name of the parameter
Returns:
named settable parameter

init

public void init(java.util.Properties map)
Parameters to be initialized. Subclasses should override if they provide any additional parameters or require additional inputs.
  1. 'name' - Name of this instance of the algorithm. Default is ''.
  2. 'relation' - type (relation) of link to calculate over. Default 'Knows'.
  3. 'actorType' - type (mode) of actor to calculate over. Deafult 'User'.
  4. 'graphClass' - graph class used to create subgraphs
  5. 'graphIDprefix' - prefix used for graphIDs.


Input 0 - Link
Output 0 - Graph

Specified by:
init in interface Component
Parameters:
map - map of the given properties naming parameters and their values in a string

findBiconnectedComponents

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.

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)


getLinks

protected Link[] getLinks(Graph g,
                          Actor v)

getOther

protected Actor getOther(Link l,
                         Actor a)