Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.algorithms.cluster
Class BicomponentClusterer

    java.lang.Object
      edu.uci.ics.jung.algorithms.cluster.BicomponentClusterer

All Implemented Interfaces:
  GraphClusterer

public class BicomponentClusterer
extends Object
implements GraphClusterer

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

Author:
  Joshua O'Madadhain
See Also:
  "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."

Field Summary
`protected int` | `converse_depth`
`protected Map` | `dfs_num`
`protected Map` | `high`
`protected Map` | `parents`
`protected Stack` | `stack`

Constructor Summary
`BicomponentClusterer()` Constructs a new bicomponent finder

Method Summary
`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, Map m)` A convenience method for getting the integer value for `v` which is stored in Map `m`.
`protected void` | `set(Vertex v, Map m, int value)` A convenience method for setting an integer value for `v` in Map `m`.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### dfs_num

    protected Map dfs_num

### high

    protected Map high

### parents

    protected Map parents

### stack

    protected Stack stack

### converse_depth

    protected int converse_depth

Constructor Detail

### BicomponentClusterer

    public BicomponentClusterer()

  Constructs a new bicomponent finder

Method Detail

### extract

    public ClusterSet extract(ArchetypeGraph theGraph)

  Extracts the bicomponents from the graph

  Specified by:
    `extract` in interface `GraphClusterer`
  Parameters:
    `theGraph` - the graph whose bicomponents are to be extracted
  Returns:
    the `ClusterSet` of bicomponents

### findBiconnectedComponents

    protected 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)

### get

    protected int get(Vertex v,
                      Map m)

  A convenience method for getting the integer value for `v` which is stored in Map `m`. Does no error checking.

### set

    protected void set(Vertex v,
                       Map m,
                       int value)

  A convenience method for setting an integer value for `v` in Map `m`.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD