KickJava   Java API By Example, From Geeks To Geeks.

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


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  * TopologicalOrderIterator.java
27  * -----------------------------
28  * (C) Copyright 2004-2006, by Marden Neubert and Contributors.
29  *
30  * Original Author: Marden Neubert
31  * Contributor(s): Barak Naveh, John V. Sichi
32  *
33  * $Id: TopologicalOrderIterator.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 17-Dec-2004 : Initial revision (MN);
38  * 25-Apr-2005 : Fixes for start vertex order (JVS);
39  * 06-Jun-2005 : Made generic (CH);
40  *
41  */
42 package org.jgrapht.traverse;
43
44 import java.util.*;
45
46 import org.jgrapht.*;
47 import org.jgrapht.util.*;
48
49
50 /**
51  * Implements topological order traversal for a directed graph. A topological
52  * sort is a permutation <tt>p</tt> of the vertices of a graph such that an edge
53  * <tt>(i,j)</tt> implies that <tt>i</tt> appears before <tt>j</tt> in <tt>
54  * p</tt> (Skiena 1990, p. 208). See also <a
55  * HREF="http://mathworld.wolfram.com/TopologicalSort.html">
56  * http://mathworld.wolfram.com/TopologicalSort.html</a>.
57  *
58  * <p>See "Algorithms in Java, Third Edition, Part 5: Graph Algorithms" by
59  * Robert Sedgewick and "Data Structures and Algorithms with Object-Oriented
60  * Design Patterns in Java" by Bruno R. Preiss for implementation alternatives.
61  * The latter can be found online at <a
62  * HREF="http://www.brpreiss.com/books/opus5/">
63  * http://www.brpreiss.com/books/opus5/</a></p>
64  *
65  * <p>For this iterator to work correctly the graph must not be modified during
66  * iteration. Currently there are no means to ensure that, nor to fail-fast. The
67  * results of such modifications are undefined.</p>
68  *
69  * @author Marden Neubert
70  * @since Dec 18, 2004
71  */
72 public class TopologicalOrderIterator<V, E>
73     extends CrossComponentIterator<V, E, Object JavaDoc>
74 {
75
76     //~ Instance fields -------------------------------------------------------
77
78     private LinkedList<V> queue;
79     private Map<V, ModifiableInteger> inDegreeMap;
80
81     //~ Constructors ----------------------------------------------------------
82
83     /**
84      * Creates a new topological order iterator over the directed graph
85      * specified. Traversal will start at one of the graphs <i>sources</i>. See
86      * the definition of source at <a
87      * HREF="http://mathworld.wolfram.com/Source.html">
88      * http://mathworld.wolfram.com/Source.html</a>.
89      *
90      * @param dg the directed graph to be iterated.
91      */
92     public TopologicalOrderIterator(DirectedGraph<V, E> dg)
93     {
94         this(dg, new LinkedList<V>(), new HashMap<V, ModifiableInteger>());
95     }
96
97     // NOTE: This is a hack to deal with the fact that CrossComponentIterator
98 // needs to know the start vertex in its constructor
99 private TopologicalOrderIterator(
100         DirectedGraph<V, E> dg,
101         LinkedList<V> queue,
102         Map<V, ModifiableInteger> inDegreeMap)
103     {
104         this(dg, initialize(dg, queue, inDegreeMap));
105         this.queue = queue;
106         this.inDegreeMap = inDegreeMap;
107     }
108
109     // NOTE: This is intentionally private, because starting the sort "in the
110 // middle" doesn't make sense.
111 private TopologicalOrderIterator(DirectedGraph<V, E> dg, V start)
112     {
113         super(dg, start);
114     }
115
116     //~ Methods ---------------------------------------------------------------
117
118     /**
119      * @see CrossComponentIterator#isConnectedComponentExhausted()
120      */
121     protected boolean isConnectedComponentExhausted()
122     {
123         // FIXME jvs 25-Apr-2005: This isn't correct for a graph with more than
124 // one component. We will actually exhaust a connected component
125 // before the queue is empty, because initialize adds roots from all
126 // components to the queue.
127 return queue.isEmpty();
128     }
129
130     /**
131      * @see CrossComponentIterator#encounterVertex(Object, Object)
132      */
133     protected void encounterVertex(V vertex, E edge)
134     {
135         putSeenData(vertex, null);
136         decrementInDegree(vertex);
137     }
138
139     /**
140      * @see CrossComponentIterator#encounterVertexAgain(Object, Object)
141      */
142     protected void encounterVertexAgain(V vertex, E edge)
143     {
144         decrementInDegree(vertex);
145     }
146
147     /**
148      * @see CrossComponentIterator#provideNextVertex()
149      */
150     protected V provideNextVertex()
151     {
152         return queue.removeFirst();
153     }
154
155     /**
156      * Decrements the in-degree of a vertex.
157      *
158      * @param vertex the vertex whose in-degree will be decremented.
159      */
160     private void decrementInDegree(V vertex)
161     {
162         ModifiableInteger inDegree = inDegreeMap.get(vertex);
163
164         if (inDegree.value > 0) {
165             inDegree.value--;
166
167             if (inDegree.value == 0) {
168                 queue.addLast(vertex);
169             }
170         }
171     }
172
173     /**
174      * Initializes the internal traversal object structure. Sets up the internal
175      * queue with the directed graph vertices and creates the control structure
176      * for the in-degrees.
177      *
178      * @param dg the directed graph to be iterated.
179      * @param queue initializer for queue
180      * @param inDegreeMap initializer for inDegreeMap
181      *
182      * @return start vertex
183      */
184     private static <V, E> V initialize(
185         DirectedGraph<V, E> dg,
186         LinkedList<V> queue,
187         Map<V, ModifiableInteger> inDegreeMap)
188     {
189         for (Iterator<V> i = dg.vertexSet().iterator(); i.hasNext();) {
190             V vertex = i.next();
191
192             int inDegree = dg.inDegreeOf(vertex);
193             inDegreeMap.put(vertex, new ModifiableInteger(inDegree));
194
195             if (inDegree == 0) {
196                 queue.add(vertex);
197             }
198         }
199
200         if (queue.isEmpty()) {
201             return null;
202         } else {
203             return queue.getFirst();
204         }
205     }
206 }
207
Popular Tags