KickJava   Java API By Example, From Geeks To Geeks.

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


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  * ConnectivityInspector.java
27  * --------------------------
28  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
29  *
30  * Original Author: Barak Naveh
31  * Contributor(s): John V. Sichi
32  * Christian Hammer
33  *
34  * $Id: ConnectivityInspector.java 504 2006-07-03 02:37:26Z perfecthash $
35  *
36  * Changes
37  * -------
38  * 06-Aug-2003 : Initial revision (BN);
39  * 10-Aug-2003 : Adaptation to new event model (BN);
40  * 07-Jun-2005 : Made generic (CH);
41  *
42  */
43 package org.jgrapht.alg;
44
45 import java.util.*;
46
47 import org.jgrapht.*;
48 import org.jgrapht.event.*;
49 import org.jgrapht.graph.*;
50 import org.jgrapht.traverse.*;
51
52
53 /**
54  * Allows obtaining various connectivity aspects of a graph. The <i>inspected
55  * graph</i> is specified at construction time and cannot be modified.
56  * Currently, the inspector supports connected components for an undirected
57  * graph and weakly connected components for a directed graph. To find strongly
58  * connected components, use {@link StrongConnectivityInspector} instead.
59  *
60  * <p>The inspector methods work in a lazy fashion: no computation is performed
61  * unless immediately necessary. Computation are done once and results and
62  * cached within this class for future need.</p>
63  *
64  * <p>The inspector is also a {@link org.jgrapht.event.GraphListener}. If added
65  * as a listener to the inspected graph, the inspector will amend internal
66  * cached results instead of recomputing them. It is efficient when a few
67  * modifications are applied to a large graph. If many modifications are
68  * expected it will not be efficient due to added overhead on graph update
69  * operations. If inspector is added as listener to a graph other than the one
70  * it inspects, results are undefined.</p>
71  *
72  * @author Barak Naveh
73  * @author John V. Sichi
74  * @since Aug 6, 2003
75  */
76 public class ConnectivityInspector<V, E>
77     implements GraphListener<V, E>
78 {
79
80     //~ Instance fields -------------------------------------------------------
81
82     List<Set<V>> connectedSets;
83     Map<V, Set<V>> vertexToConnectedSet;
84     private Graph<V, E> graph;
85
86     //~ Constructors ----------------------------------------------------------
87
88     /**
89      * Creates a connectivity inspector for the specified undirected graph.
90      *
91      * @param g the graph for which a connectivity inspector to be created.
92      */
93     public ConnectivityInspector(UndirectedGraph<V, E> g)
94     {
95         init();
96         this.graph = g;
97     }
98
99     /**
100      * Creates a connectivity inspector for the specified directed graph.
101      *
102      * @param g the graph for which a connectivity inspector to be created.
103      */
104     public ConnectivityInspector(DirectedGraph<V, E> g)
105     {
106         init();
107         this.graph = new AsUndirectedGraph<V, E>(g);
108     }
109
110     //~ Methods ---------------------------------------------------------------
111
112     /**
113      * Test if the inspected graph is connected. An empty graph is <i>not</i>
114      * considered connected.
115      *
116      * @return <code>true</code> if and only if inspected graph is connected.
117      */
118     public boolean isGraphConnected()
119     {
120         return lazyFindConnectedSets().size() == 1;
121     }
122
123     /**
124      * Returns a set of all vertices that are in the maximally connected
125      * component together with the specified vertex. For more on maximally
126      * connected component, see <a
127      * HREF="http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html">
128      * http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html</a>.
129      *
130      * @param vertex the vertex for which the connected set to be returned.
131      *
132      * @return a set of all vertices that are in the maximally connected
133      * component together with the specified vertex.
134      */
135     public Set<V> connectedSetOf(V vertex)
136     {
137         Set<V> connectedSet = vertexToConnectedSet.get(vertex);
138
139         if (connectedSet == null) {
140             connectedSet = new HashSet<V>();
141
142             BreadthFirstIterator<V, E> i =
143                 new BreadthFirstIterator<V, E>(graph, vertex);
144
145             while (i.hasNext()) {
146                 connectedSet.add(i.next());
147             }
148
149             vertexToConnectedSet.put(vertex, connectedSet);
150         }
151
152         return connectedSet;
153     }
154
155     /**
156      * Returns a list of <code>Set</code> s, where each set contains all
157      * vertices that are in the same maximally connected component. All graph
158      * vertices occur in exactly one set. For more on maximally connected
159      * component, see <a
160      * HREF="http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html">
161      * http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html</a>.
162      *
163      * @return Returns a list of <code>Set</code> s, where each set contains all
164      * vertices that are in the same maximally connected component.
165      */
166     public List<Set<V>> connectedSets()
167     {
168         return lazyFindConnectedSets();
169     }
170
171     /**
172      * @see GraphListener#edgeAdded(GraphEdgeChangeEvent)
173      */
174     public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
175     {
176         init(); // for now invalidate cached results, in the future need to
177 // amend them.
178 }
179
180     /**
181      * @see GraphListener#edgeRemoved(GraphEdgeChangeEvent)
182      */
183     public void edgeRemoved(GraphEdgeChangeEvent<V, E> e)
184     {
185         init(); // for now invalidate cached results, in the future need to
186 // amend them.
187 }
188
189     /**
190      * Tests if there is a path from the specified source vertex to the
191      * specified target vertices. For a directed graph, direction is ignored for
192      * this interpretation of path.
193      *
194      * <p>Note: Future versions of this method might not ignore edge directions
195      * for directed graphs.</p>
196      *
197      * @param sourceVertex one end of the path.
198      * @param targetVertex another end of the path.
199      *
200      * @return <code>true</code> if and only if there is a path from the source
201      * vertex to the target vertex.
202      */
203     public boolean pathExists(V sourceVertex, V targetVertex)
204     {
205         /*
206          * TODO: Ignoring edge direction for directed graph may be
207          * confusing. For directed graphs, consider Dijkstra's algorithm.
208          */
209         Set sourceSet = connectedSetOf(sourceVertex);
210
211         return sourceSet.contains(targetVertex);
212     }
213
214     /**
215      * @see VertexSetListener#vertexAdded(GraphVertexChangeEvent)
216      */
217     public void vertexAdded(GraphVertexChangeEvent<V> e)
218     {
219         init(); // for now invalidate cached results, in the future need to
220 // amend them.
221 }
222
223     /**
224      * @see VertexSetListener#vertexRemoved(GraphVertexChangeEvent)
225      */
226     public void vertexRemoved(GraphVertexChangeEvent<V> e)
227     {
228         init(); // for now invalidate cached results, in the future need to
229 // amend them.
230 }
231
232     private void init()
233     {
234         connectedSets = null;
235         vertexToConnectedSet = new HashMap<V, Set<V>>();
236     }
237
238     private List<Set<V>> lazyFindConnectedSets()
239     {
240         if (connectedSets == null) {
241             connectedSets = new ArrayList<Set<V>>();
242
243             Set vertexSet = graph.vertexSet();
244
245             if (vertexSet.size() > 0) {
246                 BreadthFirstIterator<V, E> i =
247                     new BreadthFirstIterator<V, E>(graph, null);
248                 i.addTraversalListener(new MyTraversalListener());
249
250                 while (i.hasNext()) {
251                     i.next();
252                 }
253             }
254         }
255
256         return connectedSets;
257     }
258
259     //~ Inner Classes ---------------------------------------------------------
260
261     /**
262      * A traversal listener that groups all vertices according to to their
263      * containing connected set.
264      *
265      * @author Barak Naveh
266      * @since Aug 6, 2003
267      */
268     private class MyTraversalListener
269         extends TraversalListenerAdapter<V, E>
270     {
271         private Set<V> currentConnectedSet;
272
273         /**
274          * @see TraversalListenerAdapter#connectedComponentFinished(ConnectedComponentTraversalEvent)
275          */
276         public void connectedComponentFinished(
277             ConnectedComponentTraversalEvent e)
278         {
279             connectedSets.add(currentConnectedSet);
280         }
281
282         /**
283          * @see TraversalListenerAdapter#connectedComponentStarted(ConnectedComponentTraversalEvent)
284          */
285         public void connectedComponentStarted(
286             ConnectedComponentTraversalEvent e)
287         {
288             currentConnectedSet = new HashSet<V>();
289         }
290
291         /**
292          * @see TraversalListenerAdapter#vertexTraversed(VertexTraversalEvent)
293          */
294         public void vertexTraversed(VertexTraversalEvent<V> e)
295         {
296             V v = e.getVertex();
297             currentConnectedSet.add(v);
298             vertexToConnectedSet.put(v, currentConnectedSet);
299         }
300     }
301 }
302
Popular Tags