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  ("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  (
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   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   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   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Free Books Free Magazines
Popular Tags