Package org.jgrapht.traverse
Class TopologicalOrderIterator<V,E>
- java.lang.Object
-
- org.jgrapht.traverse.AbstractGraphIterator<V,E>
-
- org.jgrapht.traverse.CrossComponentIterator<V,E,java.lang.Object>
-
- org.jgrapht.traverse.TopologicalOrderIterator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.util.Iterator<V>
,GraphIterator<V,E>
public class TopologicalOrderIterator<V,E> extends CrossComponentIterator<V,E,java.lang.Object>
Implements topological order traversal for a directed acyclic graph. A topological sort is a permutation p of the vertices of a graph such that an edge (i,j) implies that i appears before j in p (Skiena 1990, p. 208). See also http://mathworld.wolfram.com/TopologicalSort.html.See "Algorithms in Java, Third Edition, Part 5: Graph Algorithms" by Robert Sedgewick and "Data Structures and Algorithms with Object-Oriented Design Patterns in Java" by Bruno R. Preiss for implementation alternatives. The latter can be found online at http://www.brpreiss.com/books/opus5/
For this iterator to work correctly the graph must be acyclic, and must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast; the results with cyclic input (including self-loops) or concurrent modifications are undefined. To precheck a graph for cycles, consider using
CycleDetector
orKosarajuStrongConnectivityInspector
.- Since:
- Dec 18, 2004
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
TopologicalOrderIterator.LinkedListQueue<T>
-
Nested classes/interfaces inherited from class org.jgrapht.traverse.CrossComponentIterator
CrossComponentIterator.SimpleContainer<T>, CrossComponentIterator.VisitColor
-
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.DirectedSpecifics<VV,EE>, AbstractGraphIterator.FlyweightEdgeEvent<VV,localE>, AbstractGraphIterator.FlyweightVertexEvent<VV>, AbstractGraphIterator.Specifics<VV,EE>, AbstractGraphIterator.UndirectedSpecifics<VV,EE>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<V,ModifiableInteger>
inDegreeMap
private java.util.Queue<V>
queue
-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
nListeners, reusableEdgeEvent, reusableVertexEvent, specifics
-
-
Constructor Summary
Constructors Modifier Constructor Description TopologicalOrderIterator(DirectedGraph<V,E> dg)
Creates a new topological order iterator over the directed graph specified, with arbitrary tie-breaking in case of partial order.TopologicalOrderIterator(DirectedGraph<V,E> dg, java.util.Queue<V> queue)
Creates a new topological order iterator over the directed graph specified, with a user-supplied queue implementation to allow customized control over tie-breaking in case of partial order.private
TopologicalOrderIterator(DirectedGraph<V,E> dg, java.util.Queue<V> queue, java.util.Map<V,ModifiableInteger> inDegreeMap)
private
TopologicalOrderIterator(DirectedGraph<V,E> dg, V start)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
decrementInDegree(V vertex)
Decrements the in-degree of a vertex.protected void
encounterVertex(V vertex, E edge)
Update data structures the first time we see a vertex.protected void
encounterVertexAgain(V vertex, E edge)
Called whenever we re-encounter a vertex.private static <V,E>
Vinitialize(DirectedGraph<V,E> dg, java.util.Queue<V> queue, java.util.Map<V,ModifiableInteger> inDegreeMap)
Initializes the internal traversal object structure.protected boolean
isConnectedComponentExhausted()
Returns true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.protected V
provideNextVertex()
Returns the vertex to be returned in the following call to the iteratornext
method.-
Methods inherited from class org.jgrapht.traverse.CrossComponentIterator
finishVertex, getGraph, getSeenData, hasNext, isSeenVertex, next, putSeenData
-
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, createGraphSpecifics, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
-
-
-
-
Field Detail
-
queue
private java.util.Queue<V> queue
-
inDegreeMap
private java.util.Map<V,ModifiableInteger> inDegreeMap
-
-
Constructor Detail
-
TopologicalOrderIterator
public TopologicalOrderIterator(DirectedGraph<V,E> dg)
Creates a new topological order iterator over the directed graph specified, with arbitrary tie-breaking in case of partial order. Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html.- Parameters:
dg
- the directed graph to be iterated.
-
TopologicalOrderIterator
public TopologicalOrderIterator(DirectedGraph<V,E> dg, java.util.Queue<V> queue)
Creates a new topological order iterator over the directed graph specified, with a user-supplied queue implementation to allow customized control over tie-breaking in case of partial order. Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html.- Parameters:
dg
- the directed graph to be iterated.queue
- queue to use for tie-break in case of partial order (e.g. a PriorityQueue can be used to break ties according to vertex priority); must be initially empty
-
TopologicalOrderIterator
private TopologicalOrderIterator(DirectedGraph<V,E> dg, java.util.Queue<V> queue, java.util.Map<V,ModifiableInteger> inDegreeMap)
-
TopologicalOrderIterator
private TopologicalOrderIterator(DirectedGraph<V,E> dg, V start)
-
-
Method Detail
-
isConnectedComponentExhausted
protected boolean isConnectedComponentExhausted()
Description copied from class:CrossComponentIterator
Returns true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.- Specified by:
isConnectedComponentExhausted
in classCrossComponentIterator<V,E,java.lang.Object>
- Returns:
- true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.
- See Also:
CrossComponentIterator.isConnectedComponentExhausted()
-
encounterVertex
protected void encounterVertex(V vertex, E edge)
Description copied from class:CrossComponentIterator
Update data structures the first time we see a vertex.- Specified by:
encounterVertex
in classCrossComponentIterator<V,E,java.lang.Object>
- Parameters:
vertex
- the vertex encounterededge
- the edge via which the vertex was encountered, or null if the vertex is a starting point- See Also:
CrossComponentIterator.encounterVertex(Object, Object)
-
encounterVertexAgain
protected void encounterVertexAgain(V vertex, E edge)
Description copied from class:CrossComponentIterator
Called whenever we re-encounter a vertex. The default implementation does nothing.- Specified by:
encounterVertexAgain
in classCrossComponentIterator<V,E,java.lang.Object>
- Parameters:
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encountered- See Also:
CrossComponentIterator.encounterVertexAgain(Object, Object)
-
provideNextVertex
protected V provideNextVertex()
Description copied from class:CrossComponentIterator
Returns the vertex to be returned in the following call to the iteratornext
method.- Specified by:
provideNextVertex
in classCrossComponentIterator<V,E,java.lang.Object>
- Returns:
- the next vertex to be returned by this iterator.
- See Also:
CrossComponentIterator.provideNextVertex()
-
decrementInDegree
private void decrementInDegree(V vertex)
Decrements the in-degree of a vertex.- Parameters:
vertex
- the vertex whose in-degree will be decremented.
-
initialize
private static <V,E> V initialize(DirectedGraph<V,E> dg, java.util.Queue<V> queue, java.util.Map<V,ModifiableInteger> inDegreeMap)
Initializes the internal traversal object structure. Sets up the internal queue with the directed graph vertices and creates the control structure for the in-degrees.- Parameters:
dg
- the directed graph to be iterated.queue
- initializer for queueinDegreeMap
- initializer for inDegreeMap- Returns:
- start vertex
-
-