KickJava   Java API By Example, From Geeks To Geeks.

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


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