Coverage details for edu.uci.ics.jung.algorithms.cluster.BicomponentClusterer

LineHitsSource
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.Iterator;
15 import java.util.Map;
16 import java.util.Set;
17 import java.util.Stack;
18  
19 import edu.uci.ics.jung.graph.ArchetypeGraph;
20 import edu.uci.ics.jung.graph.Edge;
21 import edu.uci.ics.jung.graph.Graph;
22 import edu.uci.ics.jung.graph.Vertex;
23 import edu.uci.ics.jung.utils.PredicateUtils;
24  
25 /**
26  * Finds all biconnected components (bicomponents) of an undirected graph.
27  * A graph is a biconnected component if
28  * at least 2 vertices must be removed in order to disconnect the graph. (Graphs
29  * consisting of one vertex, or of two connected vertices, are also biconnected.) Biconnected
30  * components of three or more vertices have the property that every pair of vertices in the component
31  * are connected by two or more vertex-disjoint paths.
32  * <p>
33  * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges
34  * @see "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."
35  *
36  * @author Joshua O'Madadhain
37  */
38 public class BicomponentClusterer implements GraphClusterer
39 {
40     protected Map dfs_num;
41     protected Map high;
42     protected Map parents;
43     protected Stack stack;
44     protected int converse_depth;
45  
46     /**
47      * Constructs a new bicomponent finder
48      */
495    public BicomponentClusterer() {
505    }
51  
52     /**
53     * Extracts the bicomponents from the graph
54     * @param theGraph the graph whose bicomponents are to be extracted
55     * @return the <code>ClusterSet</code> of bicomponents
56     */
57     public ClusterSet extract(ArchetypeGraph theGraph)
58     {
595        if (!PredicateUtils.enforcesEdgeConstraint(theGraph, Graph.UNDIRECTED_EDGE)) {
600            throw new IllegalArgumentException("Algorithm currently only handles undirected graphs.");
61         }
62         
635        ClusterSet bicomponents = new VertexClusterSet(theGraph);
64  
655        if (theGraph.getVertices().isEmpty())
660            return bicomponents;
67  
68         // initialize DFS number for each vertex to 0
695        dfs_num = new HashMap();
705        for (Iterator it = theGraph.getVertices().iterator(); it.hasNext(); )
71         {
7221            Vertex v = (Vertex)it.next();
7321            set(v, dfs_num, 0);
74         }
75  
765        for (Iterator iter = theGraph.getVertices().iterator(); iter.hasNext(); )
77         {
7821            Vertex v = (Vertex)iter.next();
7921            if (get(v, dfs_num) == 0) // if we haven't hit this vertex yet...
80             {
816                high = new HashMap();
826                stack = new Stack();
836                parents = new HashMap();
846                converse_depth = theGraph.numVertices();
85                 // find the biconnected components for this subgraph, starting from v
866                findBiconnectedComponents(v, bicomponents);
87                 
88                 // if we only visited one vertex, this method won't have
89                 // ID'd it as a biconnected component, so mark it as one
906                if (theGraph.numVertices() - converse_depth == 1)
91                 {
921                    Set s = new HashSet();
931                    s.add(v);
941                    bicomponents.addCluster(s);
95                 }
96             }
97         }
98         
995        return bicomponents;
100     }
101  
102     /**
103      * <p>Stores, in <code>bicomponents</code>, all the biconnected
104      * components that are reachable from <code>v</code>.</p>
105      *
106      * <p>The algorithm basically proceeds as follows: do a depth-first
107      * traversal starting from <code>v</code>, marking each vertex with
108      * a value that indicates the order in which it was encountered (dfs_num),
109      * and with
110      * a value that indicates the highest point in the DFS tree that is known
111      * to be reachable from this vertex using non-DFS edges (high). (Since it
112      * is measured on non-DFS edges, "high" tells you how far back in the DFS
113      * tree you can reach by two distinct paths, hence biconnectivity.)
114      * Each time a new vertex w is encountered, push the edge just traversed
115      * on a stack, and call this method recursively. If w.high is no greater than
116      * v.dfs_num, then the contents of the stack down to (v,w) is a
117      * biconnected component (and v is an articulation point, that is, a
118      * component boundary). In either case, set v.high to max(v.high, w.high),
119      * and continue. If w has already been encountered but is
120      * not v's parent, set v.high max(v.high, w.dfs_num) and continue.
121      *
122      * <p>(In case anyone cares, the version of this algorithm on p. 224 of
123      * Udi Manber's "Introduction to Algorithms: A Creative Approach" seems to be
124      * wrong: the stack should be initialized outside this method,
125      * (v,w) should only be put on the stack if w hasn't been seen already,
126      * and there's no real benefit to putting v on the stack separately: just
127      * check for (v,w) on the stack rather than v. Had I known this, I could
128      * have saved myself a few days. JRTOM)</p>
129      *
130      */
131     protected void findBiconnectedComponents(Vertex v, ClusterSet bicomponents)
132     {
13321        int v_dfs_num = converse_depth;
13421        set(v, dfs_num, v_dfs_num);
13521        converse_depth--;
13621        set(v, high, v_dfs_num);
137  
13821        for (Iterator iter = v.getNeighbors().iterator(); iter.hasNext();)
139         {
14040            Vertex w = (Vertex) iter.next();
14140            int w_dfs_num = get(w, dfs_num);
14240            Edge vw = v.findEdge(w);
14340            if (w_dfs_num == 0) // w hasn't yet been visited
144             {
14515                parents.put(w, v); // v is w's parent in the DFS tree
14615                stack.push(vw);
14715                findBiconnectedComponents(w, bicomponents);
14815                int w_high = get(w, high);
14915                if (w_high <= v_dfs_num)
150                 {
151                     // v disconnects w from the rest of the graph,
152                     // i.e., v is an articulation point
153                     // thus, everything between the top of the stack and
154                     // v is part of a single biconnected component
15510                    Set bicomponent = new HashSet();
156                     Edge e;
157                     do
158                     {
15915                        e = (Edge) stack.pop();
16015                        bicomponent.addAll(e.getIncidentVertices());
161                     }
16215                    while (e != vw);
16310                    bicomponents.addCluster(bicomponent);
164                 }
16515                set(v, high, (int) Math.max(w_high, get(v, high)));
166             }
16725            else if (w != parents.get(v)) // (v,w) is a back or a forward edge
16810                set(v, high, (int) Math.max(w_dfs_num, get(v, high)));
169         }
17021    }
171  
172     /**
173      * A convenience method for getting the integer value for
174      * <code>v</code> which is stored in Map <code>m</code>.
175      * Does no error checking.
176      */
177     protected int get(Vertex v, Map m)
178     {
179101        return ((Integer)m.get(v)).intValue();
180     }
181  
182     /**
183      * A convenience method for setting an integer value
184      * for <code>v</code> in Map <code>m</code>.
185      */
186     protected void set(Vertex v, Map m, int value)
187     {
18888        m.put(v, new Integer(value));
18988    }
190 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.