Package org._3pq.jgrapht.traverse
Class TopologicalOrderIterator
- java.lang.Object
-
- org._3pq.jgrapht.traverse.AbstractGraphIterator
-
- org._3pq.jgrapht.traverse.CrossComponentIterator
-
- org._3pq.jgrapht.traverse.TopologicalOrderIterator
-
- All Implemented Interfaces:
java.util.Iterator
,GraphIterator
public class TopologicalOrderIterator extends CrossComponentIterator
Implements topological order traversal for a directed 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 not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.
- Since:
- Dec 18, 2004
- Author:
- Marden Neubert
-
-
Constructor Summary
Constructors Constructor Description TopologicalOrderIterator(DirectedGraph dg)
Creates a new topological order iterator over the directed graph specified.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected void
encounterVertex(java.lang.Object vertex, Edge edge)
Update data structures the first time we see a vertex.protected void
encounterVertexAgain(java.lang.Object vertex, Edge edge)
Called whenever we re-encounter a vertex.protected boolean
isConnectedComponentExhausted()
Returns true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.protected java.lang.Object
provideNextVertex()
Returns the vertex to be returned in the following call to the iteratornext
method.-
Methods inherited from class org._3pq.jgrapht.traverse.CrossComponentIterator
getSeenData, hasNext, isSeenVertex, next, putSeenData
-
Methods inherited from class org._3pq.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
-
-
-
-
Constructor Detail
-
TopologicalOrderIterator
public TopologicalOrderIterator(DirectedGraph dg)
Creates a new topological order iterator over the directed graph specified. Traversal will start at one of the graphs sources. See the definition of source at http://mathworld.wolfram.com/Source.html.- Parameters:
dg
- the directed graph to be iterated.
-
-
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
- 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(java.lang.Object vertex, Edge edge)
Description copied from class:CrossComponentIterator
Update data structures the first time we see a vertex.- Specified by:
encounterVertex
in classCrossComponentIterator
- 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, Edge)
-
encounterVertexAgain
protected void encounterVertexAgain(java.lang.Object vertex, Edge edge)
Description copied from class:CrossComponentIterator
Called whenever we re-encounter a vertex. The default implementation does nothing.- Specified by:
encounterVertexAgain
in classCrossComponentIterator
- Parameters:
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encountered- See Also:
CrossComponentIterator.encounterVertexAgain(Object, Edge)
-
provideNextVertex
protected java.lang.Object 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
- Returns:
- the next vertex to be returned by this iterator.
- See Also:
CrossComponentIterator.provideNextVertex()
-
-