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

Line | Hits | Source
--- | --- | ---
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 |  | `*/`
49 | 5 | `public BicomponentClusterer() {`
50 | 5 | `}`
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 |  | `{`
59 | 5 | `if (!PredicateUtils.enforcesEdgeConstraint(theGraph, Graph.UNDIRECTED_EDGE)) {`
60 | 0 | `throw new IllegalArgumentException("Algorithm currently only handles undirected graphs.");`
61 |  | `}`
62 |  | ``
63 | 5 | `ClusterSet bicomponents = new VertexClusterSet(theGraph);`
64 |  | ``
65 | 5 | `if (theGraph.getVertices().isEmpty())`
66 | 0 | `return bicomponents;`
67 |  | ``
68 |  | `// initialize DFS number for each vertex to 0`
69 | 5 | `dfs_num = new HashMap();`
70 | 5 | `for (Iterator it = theGraph.getVertices().iterator(); it.hasNext(); )`
71 |  | `{`
72 | 21 | `Vertex v = (Vertex)it.next();`
73 | 21 | `set(v, dfs_num, 0);`
74 |  | `}`
75 |  | ``
76 | 5 | `for (Iterator iter = theGraph.getVertices().iterator(); iter.hasNext(); )`
77 |  | `{`
78 | 21 | `Vertex v = (Vertex)iter.next();`
79 | 21 | `if (get(v, dfs_num) == 0) // if we haven't hit this vertex yet...`
80 |  | `{`
81 | 6 | `high = new HashMap();`
82 | 6 | `stack = new Stack();`
83 | 6 | `parents = new HashMap();`
84 | 6 | `converse_depth = theGraph.numVertices();`
85 |  | `// find the biconnected components for this subgraph, starting from v`
86 | 6 | `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`
90 | 6 | `if (theGraph.numVertices() - converse_depth == 1)`
91 |  | `{`
92 | 1 | `Set s = new HashSet();`
93 | 1 | `s.add(v);`
94 | 1 | `bicomponents.addCluster(s);`
95 |  | `}`
96 |  | `}`
97 |  | `}`
98 |  | ``
99 | 5 | `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 |  | `{`
133 | 21 | `int v_dfs_num = converse_depth;`
134 | 21 | `set(v, dfs_num, v_dfs_num);`
135 | 21 | `converse_depth--;`
136 | 21 | `set(v, high, v_dfs_num);`
137 |  | ``
138 | 21 | `for (Iterator iter = v.getNeighbors().iterator(); iter.hasNext();)`
139 |  | `{`
140 | 40 | `Vertex w = (Vertex) iter.next();`
141 | 40 | `int w_dfs_num = get(w, dfs_num);`
142 | 40 | `Edge vw = v.findEdge(w);`
143 | 40 | `if (w_dfs_num == 0) // w hasn't yet been visited`
144 |  | `{`
145 | 15 | `parents.put(w, v); // v is w's parent in the DFS tree`
146 | 15 | `stack.push(vw);`
147 | 15 | `findBiconnectedComponents(w, bicomponents);`
148 | 15 | `int w_high = get(w, high);`
149 | 15 | `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`
155 | 10 | `Set bicomponent = new HashSet();`
156 |  | `Edge e;`
157 |  | `do`
158 |  | `{`
159 | 15 | `e = (Edge) stack.pop();`
160 | 15 | `bicomponent.addAll(e.getIncidentVertices());`
161 |  | `}`
162 | 15 | `while (e != vw);`
163 | 10 | `bicomponents.addCluster(bicomponent);`
164 |  | `}`
165 | 15 | `set(v, high, (int) Math.max(w_high, get(v, high)));`
166 |  | `}`
167 | 25 | `else if (w != parents.get(v)) // (v,w) is a back or a forward edge`
168 | 10 | `set(v, high, (int) Math.max(w_dfs_num, get(v, high)));`
169 |  | `}`
170 | 21 | `}`
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 |  | `{`
179 | 101 | `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 |  | `{`
188 | 88 | `m.put(v, new Integer(value));`
189 | 88 | `}`
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.