KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > StrongConnectivityInspector


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* --------------------------
26  * StrongConnectivityInspector.java
27  * --------------------------
28  * (C) Copyright 2005-2006, by Christian Soltenborn and Contributors.
29  *
30  * Original Author: Christian Soltenborn
31  *
32  * $Id: StrongConnectivityInspector.java 504 2006-07-03 02:37:26Z perfecthash $
33  *
34  * Changes
35  * -------
36  * 2-Feb-2005 : Initial revision (CS);
37  *
38  */
39 package org.jgrapht.alg;
40
41 import java.util.*;
42
43 import org.jgrapht.*;
44 import org.jgrapht.graph.*;
45
46
47 /**
48  * <p>Complements the {@link org.jgrapht.alg.ConnectivityInspector} class with
49  * the capability to compute the strongly connected components of a directed
50  * graph. The algorithm is implemented after "Corman et al: Introduction to
51  * agorithms", Chapter 25.2. It has a running time of O(V + E).</p>
52  *
53  * <p>Unlike {@link org.jgrapht.alg.ConnectivityInspector}, this class does not
54  * implement incremental inspection. The full algorithm is executed at the first
55  * call of {@link StrongConnectivityInspector#stronglyConnectedSets()} or {@link
56  * StrongConnectivityInspector#isStronglyConnected()}.</p>
57  *
58  * @author Christian Soltenborn
59  * @author Christian Hammer
60  * @since Feb 2, 2005
61  */
62 public class StrongConnectivityInspector<V, E>
63 {
64
65     //~ Instance fields -------------------------------------------------------
66
67     // the graph to compute the strongly connected sets for
68 private final DirectedGraph<V, E> graph;
69
70     // stores the vertices, ordered by their finishing time in first dfs
71 private LinkedList<VertexData<V>> orderedVertices;
72
73     // the result of the computation, cached for future calls
74 private List<Set<V>> stronglyConnectedSets;
75
76     // the result of the computation, cached for future calls
77 private List<DirectedSubgraph<V, E>> stronglyConnectedSubgraphs;
78
79     // maps vertices to their VertexData object
80 private Map<V, VertexData<V>> vertexToVertexData;
81
82     //~ Constructors ----------------------------------------------------------
83
84     /**
85      * The constructor of the StrongConnectivityInspector class.
86      *
87      * @param directedGraph the graph to inspect
88      *
89      * @throws IllegalArgumentException
90      */
91     public StrongConnectivityInspector(DirectedGraph<V, E> directedGraph)
92     {
93         if (directedGraph == null) {
94             throw new IllegalArgumentException JavaDoc("null not allowed for graph!");
95         }
96
97         graph = directedGraph;
98         vertexToVertexData = null;
99         orderedVertices = null;
100         stronglyConnectedSets = null;
101         stronglyConnectedSubgraphs = null;
102     }
103
104     //~ Methods ---------------------------------------------------------------
105
106     /**
107      * Returns the graph inspected by the StrongConnectivityInspector.
108      *
109      * @return the graph inspected by this StrongConnectivityInspector
110      */
111     public DirectedGraph<V, E> getGraph()
112     {
113         return graph;
114     }
115
116     /**
117      * Returns true if the graph of this <code>
118      * StronglyConnectivityInspector</code> instance is strongly connected.
119      *
120      * @return true if the graph is strongly connected, false otherwise
121      */
122     public boolean isStronglyConnected()
123     {
124         return stronglyConnectedSets().size() == 1;
125     }
126
127     /**
128      * Computes a {@link List} of {@link Set}s, where each set contains vertices
129      * which together form a strongly connected component within the given
130      * graph.
131      *
132      * @return <code>List</code> of <code>Set</code> s containing the strongly
133      * connected components
134      */
135     public List<Set<V>> stronglyConnectedSets()
136     {
137         if (stronglyConnectedSets == null) {
138             orderedVertices = new LinkedList<VertexData<V>>();
139             stronglyConnectedSets = new Vector<Set<V>>();
140
141             // create VertexData objects for all vertices, store them
142 createVertexData();
143
144             // perform the first round of DFS, result is an ordering
145 // of the vertices by decreasing finishing time
146 Iterator<VertexData<V>> iter =
147                 vertexToVertexData.values().iterator();
148
149             while (iter.hasNext()) {
150                 VertexData<V> data = iter.next();
151
152                 if (!data.discovered) {
153                     dfsVisit(graph, data, null);
154                 }
155             }
156
157             // calculate inverse graph (i.e. every edge is reversed)
158 DirectedGraph<V, E> inverseGraph =
159                 new DefaultDirectedGraph<V, E>(graph.getEdgeFactory());
160             Graphs.addGraphReversed(inverseGraph, graph);
161
162             // get ready for next dfs round
163 resetVertexData();
164
165             // second dfs round: vertices are considered in decreasing
166 // finishing time order; every tree found is a strongly
167 // connected set
168 iter = orderedVertices.iterator();
169
170             while (iter.hasNext()) {
171                 VertexData<V> data = iter.next();
172
173                 if (!data.discovered) {
174                     // new strongly connected set
175 Set<V> set = new HashSet<V>();
176                     stronglyConnectedSets.add(set);
177                     dfsVisit(inverseGraph, data, set);
178                 }
179             }
180
181             // clean up for garbage collection
182 orderedVertices = null;
183             vertexToVertexData = null;
184         }
185
186         return stronglyConnectedSets;
187     }
188
189     /**
190      * <p>Computes a list of {@link DirectedSubgraph}s of the given graph. Each
191      * subgraph will represent a strongly connected component and will contain
192      * all vertices of that component. The subgraph will have an edge (u,v) iff
193      * u and v are contained in the strongly connected component.</p>
194      *
195      * <p>NOTE: Calling this method will first execute {@link
196      * StrongConnectivityInspector#stronglyConnectedSets()}. If you don't need
197      * subgraphs, use that method.</p>
198      *
199      * @return a list of subgraphs representing the strongly connected
200      * components
201      */
202     public List<DirectedSubgraph<V, E>> stronglyConnectedSubgraphs()
203     {
204         if (stronglyConnectedSubgraphs == null) {
205             List<Set<V>> sets = stronglyConnectedSets();
206             stronglyConnectedSubgraphs =
207                 new Vector<DirectedSubgraph<V, E>>(sets.size());
208
209             Iterator<Set<V>> iter = sets.iterator();
210
211             while (iter.hasNext()) {
212                 stronglyConnectedSubgraphs.add(
213                     new DirectedSubgraph<V, E>(
214                         graph,
215                         iter.next(),
216                         null));
217             }
218         }
219
220         return stronglyConnectedSubgraphs;
221     }
222
223     /*
224      * Creates a VertexData object for every vertex in the graph and stores
225      * them
226      * in a HashMap.
227      */
228     private void createVertexData()
229     {
230         vertexToVertexData =
231             new HashMap<V, VertexData<V>>(graph.vertexSet().size());
232
233         Iterator<V> iter = graph.vertexSet().iterator();
234
235         while (iter.hasNext()) {
236             V vertex = iter.next();
237             vertexToVertexData.put(
238                 vertex,
239                 new VertexData<V>(null, vertex, false, false));
240         }
241     }
242
243     /*
244      * The subroutine of DFS. NOTE: the set is used to distinguish between 1st
245      * and 2nd round of DFS. set == null: finished vertices are stored (1st
246      * round). set != null: all vertices found will be saved in the set (2nd
247      * round)
248      */
249     private void dfsVisit(
250         DirectedGraph<V, E> graph,
251         VertexData<V> vertexData,
252         Set<V> vertices)
253     {
254         Stack<VertexData<V>> stack = new Stack<VertexData<V>>();
255         stack.push(vertexData);
256
257         while (!stack.isEmpty()) {
258             VertexData<V> data = stack.pop();
259
260             if (!data.discovered) {
261                 data.discovered = true;
262
263                 if (vertices != null) {
264                     vertices.add(data.vertex);
265                 }
266
267                 stack.push(new VertexData<V>(data, null, true, true));
268
269                 // follow all edges
270 Iterator<? extends E> iter =
271                     graph.outgoingEdgesOf(data.vertex).iterator();
272
273                 while (iter.hasNext()) {
274                     E edge = iter.next();
275                     VertexData<V> targetData =
276                         vertexToVertexData.get(this.graph.getEdgeTarget(edge));
277
278                     if (!targetData.discovered) {
279                         // the "recursion"
280 stack.push(targetData);
281                     }
282                 }
283             } else if (data.finished) {
284                 if (vertices == null) {
285                     orderedVertices.addFirst(data.finishedData);
286                 }
287             }
288         }
289     }
290
291     /*
292      * Resets all VertexData objects.
293      */
294     private void resetVertexData()
295     {
296         Iterator<VertexData<V>> iter = vertexToVertexData.values().iterator();
297
298         while (iter.hasNext()) {
299             VertexData<V> data = iter.next();
300             data.discovered = false;
301             data.finished = false;
302         }
303     }
304
305     //~ Inner Classes ---------------------------------------------------------
306
307     /*
308      * Lightweight class storing some data for every vertex.
309      */
310     private static final class VertexData<V>
311     {
312         // TODO jvs 24-June-2006: more compact representation;
313 // I added finishedData to clean up the generics warnings
314 private final VertexData<V> finishedData;
315         private final V vertex;
316         private boolean discovered;
317         private boolean finished;
318
319         private VertexData(
320             VertexData<V> finishedData,
321             V vertex,
322             boolean discovered,
323             boolean finished)
324         {
325             this.finishedData = finishedData;
326             this.vertex = vertex;
327             this.discovered = discovered;
328             this.finished = finished;
329         }
330     }
331 }
332
Popular Tags