/* * Copyright (c) 2003, the JUNG Project and the Regents of the University * of California * All rights reserved. * * This software is open-source under the BSD license; see either * "license.txt" or * http://jung.sourceforge.net/license.txt for a description. */ package edu.uci.ics.jung.algorithms.cluster; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.Map; import java.util.Set; import java.util.Stack; import org.apache.commons.collections15.Transformer; import edu.uci.ics.jung.graph.UndirectedGraph; /** * 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 "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."
*
* @author Joshua O'Madadhain
*/
public class BicomponentClusterer Stores, in The algorithm basically proceeds as follows: do a depth-first
* traversal starting from (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)ClusterSet
of bicomponents
*/
public Setbicomponents
, all the biconnected
* components that are reachable from v
.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.
*
*