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. |
copyright © 2003, jcoverage ltd. all rights reserved. |