org._3pq.jgrapht.traverse
public class TopologicalOrderIterator extends CrossComponentIterator
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.
Constructor and Description |
---|
TopologicalOrderIterator(DirectedGraph dg)
Creates a new topological order iterator over the directed graph
specified.
|
Modifier and Type | Method and 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 iterator
next method. |
getSeenData, hasNext, isSeenVertex, next, putSeenData
addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
public TopologicalOrderIterator(DirectedGraph dg)
dg
- the directed graph to be iterated.protected boolean isConnectedComponentExhausted()
CrossComponentIterator
isConnectedComponentExhausted
in class CrossComponentIterator
CrossComponentIterator.isConnectedComponentExhausted()
protected void encounterVertex(java.lang.Object vertex, Edge edge)
CrossComponentIterator
encounterVertex
in class CrossComponentIterator
vertex
- the vertex encounterededge
- the edge via which the vertex was encountered, or null if
the vertex is a starting pointCrossComponentIterator.encounterVertex(Object, Edge)
protected void encounterVertexAgain(java.lang.Object vertex, Edge edge)
CrossComponentIterator
encounterVertexAgain
in class CrossComponentIterator
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encounteredCrossComponentIterator.encounterVertexAgain(Object, Edge)
protected java.lang.Object provideNextVertex()
CrossComponentIterator
next
method.provideNextVertex
in class CrossComponentIterator
CrossComponentIterator.provideNextVertex()