KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > traverse > CrossComponentIterator


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  * CrossComponentIterator.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: CrossComponentIterator.java 504 2006-07-03 02:37:26Z perfecthash $
35  *
36  * Changes
37  * -------
38  * 31-Jul-2003 : Initial revision (BN);
39  * 11-Aug-2003 : Adaptation to new event model (BN);
40  * 31-Jan-2004 : Extracted cross-component traversal functionality (BN);
41  * 04-May-2004 : Made generic (CH)
42  * 07-May-2006 : Changed from List<Edge> to Set<Edge> (JVS);
43  *
44  */

45 package org.jgrapht.traverse;
46
47 import java.util.*;
48
49 import org.jgrapht.*;
50 import org.jgrapht.event.*;
51
52
53 /**
54  * Provides a cross-connected-component traversal functionality for iterator
55  * subclasses.
56  *
57  * @param <V> vertex type
58  * @param <E> edge type
59  * @param <D> type of data associated to seen vertices
60  *
61  * @author Barak Naveh
62  * @since Jan 31, 2004
63  */

64 public abstract class CrossComponentIterator<V, E, D>
65     extends AbstractGraphIterator<V, E>
66 {
67
68     //~ Static fields/initializers --------------------------------------------
69

70     private static final int CCS_BEFORE_COMPONENT = 1;
71     private static final int CCS_WITHIN_COMPONENT = 2;
72     private static final int CCS_AFTER_COMPONENT = 3;
73
74     //~ Instance fields -------------------------------------------------------
75

76     //
77
private final ConnectedComponentTraversalEvent ccFinishedEvent =
78         new ConnectedComponentTraversalEvent(
79             this,
80             ConnectedComponentTraversalEvent.CONNECTED_COMPONENT_FINISHED);
81     private final ConnectedComponentTraversalEvent ccStartedEvent =
82         new ConnectedComponentTraversalEvent(
83             this,
84             ConnectedComponentTraversalEvent.CONNECTED_COMPONENT_STARTED);
85
86     // TODO: support ConcurrentModificationException if graph modified
87
// during iteration.
88
private FlyweightEdgeEvent<V, E> reusableEdgeEvent;
89     private FlyweightVertexEvent<V> reusableVertexEvent;
90     private Iterator<V> vertexIterator = null;
91
92     /**
93      * Stores the vertices that have been seen during iteration and (optionally)
94      * some additional traversal info regarding each vertex.
95      */

96     private Map<V, D> seen = new HashMap<V, D>();
97     private V startVertex;
98     private Specifics<V, E> specifics;
99
100     private final Graph<V, E> graph;
101
102     /**
103      * The connected component state
104      */

105     private int state = CCS_BEFORE_COMPONENT;
106
107     //~ Constructors ----------------------------------------------------------
108

109     /**
110      * Creates a new iterator for the specified graph. Iteration will start at
111      * the specified start vertex. If the specified start vertex is <code>
112      * null</code>, Iteration will start at an arbitrary graph vertex.
113      *
114      * @param g the graph to be iterated.
115      * @param startVertex the vertex iteration to be started.
116      *
117      * @throws IllegalArgumentException if <code>g==null</code> or does not
118      * contain <code>startVertex</code>
119      */

120     public CrossComponentIterator(Graph<V, E> g, V startVertex)
121     {
122         super();
123
124         if (g == null) {
125             throw new IllegalArgumentException JavaDoc("graph must not be null");
126         }
127         graph = g;
128
129         specifics = createGraphSpecifics(g);
130         vertexIterator = g.vertexSet().iterator();
131         setCrossComponentTraversal(startVertex == null);
132
133         reusableEdgeEvent = new FlyweightEdgeEvent<V, E>(this, null);
134         reusableVertexEvent = new FlyweightVertexEvent<V>(this, null);
135
136         if (startVertex == null) {
137             // pick a start vertex if graph not empty
138
if (vertexIterator.hasNext()) {
139                 this.startVertex = vertexIterator.next();
140             } else {
141                 this.startVertex = null;
142             }
143         } else if (g.containsVertex(startVertex)) {
144             this.startVertex = startVertex;
145         } else {
146             throw new IllegalArgumentException JavaDoc(
147                 "graph must contain the start vertex");
148         }
149     }
150
151     //~ Methods ---------------------------------------------------------------
152

153     /**
154      * @return the graph being traversed
155      */

156     public Graph<V, E> getGraph()
157     {
158         return graph;
159     }
160
161     /**
162      * @see java.util.Iterator#hasNext()
163      */

164     public boolean hasNext()
165     {
166         if (startVertex != null) {
167             encounterStartVertex();
168         }
169
170         if (isConnectedComponentExhausted()) {
171             if (state == CCS_WITHIN_COMPONENT) {
172                 state = CCS_AFTER_COMPONENT;
173                 fireConnectedComponentFinished(ccFinishedEvent);
174             }
175
176             if (isCrossComponentTraversal()) {
177                 while (vertexIterator.hasNext()) {
178                     V v = vertexIterator.next();
179
180                     if (!isSeenVertex(v)) {
181                         encounterVertex(v, null);
182                         state = CCS_BEFORE_COMPONENT;
183
184                         return true;
185                     }
186                 }
187
188                 return false;
189             } else {
190                 return false;
191             }
192         } else {
193             return true;
194         }
195     }
196
197     /**
198      * @see java.util.Iterator#next()
199      */

200     public V next()
201     {
202         if (startVertex != null) {
203             encounterStartVertex();
204         }
205
206         if (hasNext()) {
207             if (state == CCS_BEFORE_COMPONENT) {
208                 state = CCS_WITHIN_COMPONENT;
209                 fireConnectedComponentStarted(ccStartedEvent);
210             }
211
212             V nextVertex = provideNextVertex();
213             fireVertexTraversed(createVertexTraversalEvent(nextVertex));
214
215             addUnseenChildrenOf(nextVertex);
216
217             return nextVertex;
218         } else {
219             throw new NoSuchElementException();
220         }
221     }
222
223     /**
224      * Returns <tt>true</tt> if there are no more uniterated vertices in the
225      * currently iterated connected component; <tt>false</tt> otherwise.
226      *
227      * @return <tt>true</tt> if there are no more uniterated vertices in the
228      * currently iterated connected component; <tt>false</tt> otherwise.
229      */

230     protected abstract boolean isConnectedComponentExhausted();
231
232     /**
233      * Update data structures the first time we see a vertex.
234      *
235      * @param vertex the vertex encountered
236      * @param edge the edge via which the vertex was encountered, or null if the
237      * vertex is a starting point
238      */

239     protected abstract void encounterVertex(V vertex, E edge);
240
241     /**
242      * Returns the vertex to be returned in the following call to the iterator
243      * <code>next</code> method.
244      *
245      * @return the next vertex to be returned by this iterator.
246      */

247     protected abstract V provideNextVertex();
248
249     /**
250      * Access the data stored for a seen vertex.
251      *
252      * @param vertex a vertex which has already been seen.
253      *
254      * @return data associated with the seen vertex or <code>null</code> if no
255      * data was associated with the vertex. A <code>null</code> return
256      * can also indicate that the vertex was explicitly associated with
257      * <code>null</code>.
258      */

259     protected D getSeenData(V vertex)
260     {
261         return seen.get(vertex);
262     }
263
264     /**
265      * Determines whether a vertex has been seen yet by this traversal.
266      *
267      * @param vertex vertex in question
268      *
269      * @return <tt>true</tt> if vertex has already been seen
270      */

271     protected boolean isSeenVertex(Object JavaDoc vertex)
272     {
273         return seen.containsKey(vertex);
274     }
275
276     /**
277      * Called whenever we re-encounter a vertex. The default implementation
278      * does nothing.
279      *
280      * @param vertex the vertex re-encountered
281      * @param edge the edge via which the vertex was re-encountered
282      */

283     protected abstract void encounterVertexAgain(V vertex, E edge);
284
285     /**
286      * Stores iterator-dependent data for a vertex that has been seen.
287      *
288      * @param vertex a vertex which has been seen.
289      * @param data data to be associated with the seen vertex.
290      *
291      * @return previous value associated with specified vertex or <code>
292      * null</code> if no data was associated with the vertex. A <code>
293      * null</code> return can also indicate that the vertex was
294      * explicitly associated with <code>null</code>.
295      */

296     protected D putSeenData(V vertex, D data)
297     {
298         return seen.put(vertex, data);
299     }
300
301     // -------------------------------------------------------------------------
302
/**
303      * @param <V>
304      * @param <E>
305      * @param g
306      *
307      * @return TODO Document me
308      */

309     static <V, E> Specifics<V, E> createGraphSpecifics(Graph<V, E> g)
310     {
311         if (g instanceof DirectedGraph) {
312             return new DirectedSpecifics<V, E>((DirectedGraph<V, E>) g);
313         } else {
314             return new UndirectedSpecifics<V, E>(g);
315         }
316     }
317
318     private void addUnseenChildrenOf(V vertex)
319     {
320         for (E edge : specifics.edgesOf(vertex)) {
321             fireEdgeTraversed(createEdgeTraversalEvent(edge));
322
323             V oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
324
325             if (isSeenVertex(oppositeV)) {
326                 encounterVertexAgain(oppositeV, edge);
327             } else {
328                 encounterVertex(oppositeV, edge);
329             }
330         }
331     }
332
333     private EdgeTraversalEvent<V, E> createEdgeTraversalEvent(E edge)
334     {
335         if (isReuseEvents()) {
336             reusableEdgeEvent.setEdge(edge);
337
338             return reusableEdgeEvent;
339         } else {
340             return new EdgeTraversalEvent<V, E>(this, edge);
341         }
342     }
343
344     private VertexTraversalEvent<V> createVertexTraversalEvent(V vertex)
345     {
346         if (isReuseEvents()) {
347             reusableVertexEvent.setVertex(vertex);
348
349             return reusableVertexEvent;
350         } else {
351             return new VertexTraversalEvent<V>(this, vertex);
352         }
353     }
354
355     private void encounterStartVertex()
356     {
357         encounterVertex(startVertex, null);
358         startVertex = null;
359     }
360
361     //~ Inner Interfaces ------------------------------------------------------
362

363     static interface SimpleContainer<T>
364     {
365         /**
366          * Tests if this container is empty.
367          *
368          * @return <code>true</code> if empty, otherwise <code>false</code>.
369          */

370         public boolean isEmpty();
371
372         /**
373          * Adds the specified object to this container.
374          *
375          * @param o the object to be added.
376          */

377         public void add(T o);
378
379         /**
380          * Remove an object from this container and return it.
381          *
382          * @return the object removed from this container.
383          */

384         public T remove();
385     }
386
387     //~ Inner Classes ---------------------------------------------------------
388

389     /**
390      * Provides unified interface for operations that are different in directed
391      * graphs and in undirected graphs.
392      */

393     abstract static class Specifics<VV, EE>
394     {
395         /**
396          * Returns the edges outgoing from the specified vertex in case of
397          * directed graph, and the edge touching the specified vertex in case of
398          * undirected graph.
399          *
400          * @param vertex the vertex whose outgoing edges are to be returned.
401          *
402          * @return the edges outgoing from the specified vertex in case of
403          * directed graph, and the edge touching the specified vertex in
404          * case of undirected graph.
405          */

406         public abstract Set<? extends EE> edgesOf(VV vertex);
407     }
408
409     /**
410      * A reusable edge event.
411      *
412      * @author Barak Naveh
413      * @since Aug 11, 2003
414      */

415     static class FlyweightEdgeEvent<VV, localE>
416         extends EdgeTraversalEvent<VV, localE>
417     {
418         private static final long serialVersionUID = 4051327833765000755L;
419
420         /**
421          * @see EdgeTraversalEvent#EdgeTraversalEvent(Object, Edge)
422          */

423         public FlyweightEdgeEvent(Object JavaDoc eventSource, localE edge)
424         {
425             super(eventSource, edge);
426         }
427
428         /**
429          * Sets the edge of this event.
430          *
431          * @param edge the edge to be set.
432          */

433         protected void setEdge(localE edge)
434         {
435             this.edge = edge;
436         }
437     }
438
439     /**
440      * A reusable vertex event.
441      *
442      * @author Barak Naveh
443      * @since Aug 11, 2003
444      */

445     static class FlyweightVertexEvent<VV>
446         extends VertexTraversalEvent<VV>
447     {
448         private static final long serialVersionUID = 3834024753848399924L;
449
450         /**
451          * @see VertexTraversalEvent#VertexTraversalEvent(Object, Object)
452          */

453         public FlyweightVertexEvent(Object JavaDoc eventSource, VV vertex)
454         {
455             super(eventSource, vertex);
456         }
457
458         /**
459          * Sets the vertex of this event.
460          *
461          * @param vertex the vertex to be set.
462          */

463         protected void setVertex(VV vertex)
464         {
465             this.vertex = vertex;
466         }
467     }
468
469     /**
470      * An implementation of {@link Specifics} for a directed graph.
471      */

472     private static class DirectedSpecifics<VV, EE>
473         extends Specifics<VV, EE>
474     {
475         private DirectedGraph<VV, EE> graph;
476
477         /**
478          * Creates a new DirectedSpecifics object.
479          *
480          * @param g the graph for which this specifics object to be created.
481          */

482         public DirectedSpecifics(DirectedGraph<VV, EE> g)
483         {
484             graph = g;
485         }
486
487         /**
488          * @see CrossComponentIterator.Specifics#edgesOf(Object)
489          */

490         public Set<? extends EE> edgesOf(VV vertex)
491         {
492             return graph.outgoingEdgesOf(vertex);
493         }
494     }
495
496     /**
497      * An implementation of {@link Specifics} in which edge direction (if any)
498      * is ignored.
499      */

500     private static class UndirectedSpecifics<VV, EE>
501         extends Specifics<VV, EE>
502     {
503         private Graph<VV, EE> graph;
504
505         /**
506          * Creates a new UndirectedSpecifics object.
507          *
508          * @param g the graph for which this specifics object to be created.
509          */

510         public UndirectedSpecifics(Graph<VV, EE> g)
511         {
512             graph = g;
513         }
514
515         /**
516          * @see CrossComponentIterator.Specifics#edgesOf(Object)
517          */

518         public Set<EE> edgesOf(VV vertex)
519         {
520             return graph.edgesOf(vertex);
521         }
522     }
523 }
524
Popular Tags