KickJava   Java API By Example, From Geeks To Geeks.

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


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  * BreadthFirstIterator.java
27  * -------------------------
28  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
29  *
30  * Original Author: Barak Naveh
31  * Contributor(s): Liviu Rau
32  * Christian Hammer
33  *
34  * $Id: BreadthFirstIterator.java 504 2006-07-03 02:37:26Z perfecthash $
35  *
36  * Changes
37  * -------
38  * 24-Jul-2003 : Initial revision (BN);
39  * 06-Aug-2003 : Extracted common logic to TraverseUtils.XXFirstIterator (BN);
40  * 31-Jan-2004 : Reparented and changed interface to parent class (BN);
41  *
42  */
43 package org.jgrapht.traverse;
44
45 import java.util.*;
46
47 import org.jgrapht.*;
48
49
50 /**
51  * A breadth-first iterator for a directed and an undirected graph. For this
52  * iterator to work correctly the graph must not be modified during iteration.
53  * Currently there are no means to ensure that, nor to fail-fast. The results of
54  * such modifications are undefined.
55  *
56  * @author Barak Naveh
57  * @since Jul 19, 2003
58  */
59 public class BreadthFirstIterator<V, E>
60     extends CrossComponentIterator<V, E, Object JavaDoc>
61 {
62
63     //~ Instance fields -------------------------------------------------------
64
65     /**
66      * <b>Note to users:</b> this queue implementation is a bit lame in terms of
67      * GC efficiency. If you need it to be improved either let us know or use
68      * the source...
69      */
70     private LinkedList<V> queue = new LinkedList<V>();
71
72     //~ Constructors ----------------------------------------------------------
73
74     /**
75      * Creates a new breadth-first iterator for the specified graph.
76      *
77      * @param g the graph to be iterated.
78      */
79     public BreadthFirstIterator(Graph<V, E> g)
80     {
81         this(g, null);
82     }
83
84     /**
85      * Creates a new breadth-first iterator for the specified graph. Iteration
86      * will start at the specified start vertex and will be limited to the
87      * connected component that includes that vertex. If the specified start
88      * vertex is <code>null</code>, iteration will start at an arbitrary vertex
89      * and will not be limited, that is, will be able to traverse all the graph.
90      *
91      * @param g the graph to be iterated.
92      * @param startVertex the vertex iteration to be started.
93      */
94     public BreadthFirstIterator(Graph<V, E> g, V startVertex)
95     {
96         super(g, startVertex);
97     }
98
99     //~ Methods ---------------------------------------------------------------
100
101     /**
102      * @see CrossComponentIterator#isConnectedComponentExhausted()
103      */
104     protected boolean isConnectedComponentExhausted()
105     {
106         return queue.isEmpty();
107     }
108
109     /**
110      * @see CrossComponentIterator#encounterVertex(Object, Object)
111      */
112     protected void encounterVertex(V vertex, E edge)
113     {
114         putSeenData(vertex, null);
115         queue.add(vertex);
116     }
117
118     /**
119      * @see CrossComponentIterator#encounterVertexAgain(Object, Object)
120      */
121     protected void encounterVertexAgain(V vertex, E edge)
122     {
123     }
124
125     /**
126      * @see CrossComponentIterator#provideNextVertex()
127      */
128     protected V provideNextVertex()
129     {
130         return queue.removeFirst();
131     }
132 }
133
Popular Tags