third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/BicomponentClusterer.java

   1 /*
   2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3 * of California
   4 * All rights reserved.
   5 *
   6 * This software is open-source under the BSD license; see either
   7 * "license.txt" or
   8 * http://jung.sourceforge.net/license.txt for a description.
   9 */
  10 package edu.uci.ics.jung.algorithms.cluster;
  11
  12 import java.util.HashMap;
  13 import java.util.HashSet;
  14 import java.util.LinkedHashSet;
  15 import java.util.Map;
  16 import java.util.Set;
  17 import java.util.Stack;
  18
  19 import org.apache.commons.collections15.Transformer;
  20
  21 import edu.uci.ics.jung.graph.UndirectedGraph;
  22
  23 /**
  24  * Finds all biconnected components (bicomponents) of an undirected graph.
  25  * A graph is a biconnected component if
  26  * at least 2 vertices must be removed in order to disconnect the graph.  (Graphs
  27  * consisting of one vertex, or of two connected vertices, are also biconnected.)  Biconnected
  28  * components of three or more vertices have the property that every pair of vertices in the component
  29  * are connected by two or more vertex-disjoint paths.
  30  * <p>
  31  * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges
  32  * @see "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."
  33  *
  34  * @author Joshua O'Madadhain
  35  */
  36 public class BicomponentClusterer<V,E> implements Transformer<UndirectedGraph<V,E>, Set<Set<V>>>
  37 {
  38     protected Map<V,Number> dfs_num;
  39     protected Map<V,Number> high;
  40     protected Map<V,V> parents;
  41     protected Stack<E> stack;
  42     protected int converse_depth;
  43
  44     /**
  45      * Constructs a new bicomponent finder
  46      */
  47     public BicomponentClusterer() {
  48     }
  49
  50     /**
  51     * Extracts the bicomponents from the graph.
  52     * @param theGraph the graph whose bicomponents are to be extracted
  53     * @return the <code>ClusterSet</code> of bicomponents
  54     */
  55     public Set<Set<V>> transform(UndirectedGraph<V,E> theGraph)
  56     {
  57         Set<Set<V>> bicomponents = new LinkedHashSet<Set<V>>();
  58
  59         if (theGraph.getVertices().isEmpty())
  60             return bicomponents;
  61
  62         // initialize DFS number for each vertex to 0
  63         dfs_num = new HashMap<V,Number>();
  64         for (V v : theGraph.getVertices())
  65         {
  66                 dfs_num.put(v, 0);
  67         }
  68
  69         for (V v : theGraph.getVertices())
  70         {
  71             if (dfs_num.get(v).intValue() == 0) // if we haven't hit this vertex yet...
  72             {
  73                 high = new HashMap<V,Number>();
  74                 stack = new Stack<E>();
  75                 parents = new HashMap<V,V>();
  76                 converse_depth = theGraph.getVertexCount();
  77                 // find the biconnected components for this subgraph, starting from v
  78                 findBiconnectedComponents(theGraph, v, bicomponents);
  79
  80                 // if we only visited one vertex, this method won't have
  81                 // ID'd it as a biconnected component, so mark it as one
  82                 if (theGraph.getVertexCount() - converse_depth == 1)
  83                 {
  84                     Set<V> s = new HashSet<V>();
  85                     s.add(v);
  86                     bicomponents.add(s);
  87                 }
  88             }
  89         }
  90
  91         return bicomponents;
  92     }
  93
  94     /**
  95      * <p>Stores, in <code>bicomponents</code>, all the biconnected
  96      * components that are reachable from <code>v</code>.</p>
  97      *
  98      * <p>The algorithm basically proceeds as follows: do a depth-first
  99      * traversal starting from <code>v</code>, marking each vertex with
 100      * a value that indicates the order in which it was encountered (dfs_num),
 101      * and with
 102      * a value that indicates the highest point in the DFS tree that is known
 103      * to be reachable from this vertex using non-DFS edges (high).  (Since it
 104      * is measured on non-DFS edges, "high" tells you how far back in the DFS
 105      * tree you can reach by two distinct paths, hence biconnectivity.)
 106      * Each time a new vertex w is encountered, push the edge just traversed
 107      * on a stack, and call this method recursively.  If w.high is no greater than
 108      * v.dfs_num, then the contents of the stack down to (v,w) is a
 109      * biconnected component (and v is an articulation point, that is, a
 110      * component boundary).  In either case, set v.high to max(v.high, w.high),
 111      * and continue.  If w has already been encountered but is
 112      * not v's parent, set v.high max(v.high, w.dfs_num) and continue.
 113      *
 114      * <p>(In case anyone cares, the version of this algorithm on p. 224 of
 115      * Udi Manber's "Introduction to Algorithms: A Creative Approach" seems to be
 116      * wrong: the stack should be initialized outside this method,
 117      * (v,w) should only be put on the stack if w hasn't been seen already,
 118      * and there's no real benefit to putting v on the stack separately: just
 119      * check for (v,w) on the stack rather than v.  Had I known this, I could
 120      * have saved myself a few days.  JRTOM)</p>
 121      *
 122      */
 123     protected void findBiconnectedComponents(UndirectedGraph<V,E> g, V v, Set<Set<V>> bicomponents)
 124     {
 125         int v_dfs_num = converse_depth;
 126         dfs_num.put(v, v_dfs_num);
 127         converse_depth--;
 128         high.put(v, v_dfs_num);
 129
 130         for (V w : g.getNeighbors(v))
 131         {
 132             int w_dfs_num = dfs_num.get(w).intValue();//get(w, dfs_num);
 133             E vw = g.findEdge(v,w);
 134             if (w_dfs_num == 0) // w hasn't yet been visited
 135             {
 136                 parents.put(w, v); // v is w's parent in the DFS tree
 137                 stack.push(vw);
 138                 findBiconnectedComponents(g, w, bicomponents);
 139                 int w_high = high.get(w).intValue();//get(w, high);
 140                 if (w_high <= v_dfs_num)
 141                 {
 142                     // v disconnects w from the rest of the graph,
 143                     // i.e., v is an articulation point
 144                     // thus, everything between the top of the stack and
 145                     // v is part of a single biconnected component
 146                     Set<V> bicomponent = new HashSet<V>();
 147                     E e;
 148                     do
 149                     {
 150                         e = stack.pop();
 151                         bicomponent.addAll(g.getIncidentVertices(e));
 152                     }
 153                     while (e != vw);
 154                     bicomponents.add(bicomponent);
 155                 }
 156                 high.put(v, Math.max(w_high, high.get(v).intValue()));
 157             }
 158             else if (w != parents.get(v)) // (v,w) is a back or a forward edge
 159                 high.put(v, Math.max(w_dfs_num, high.get(v).intValue()));
 160         }
 161     }
 162 }