V
 the graph vertex typeE
 the graph edge typepublic class TopologicalOrderIterator<V,E> extends CrossComponentIterator<V,E,Object>
See "Algorithms in Java, Third Edition, Part 5: Graph Algorithms" by Robert Sedgewick and "Data Structures and Algorithms with ObjectOriented 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 failfast; the results with cyclic
input (including selfloops) or concurrent modifications are undefined. To precheck a graph for
cycles, consider using CycleDetector
or
KosarajuStrongConnectivityInspector
.
CrossComponentIterator.VisitColor
nListeners, reusableEdgeEvent, reusableVertexEvent, specifics
Constructor and Description 

TopologicalOrderIterator(DirectedGraph<V,E> dg)
Creates a new topological order iterator over the directed graph specified, with arbitrary
tiebreaking in case of partial order.

TopologicalOrderIterator(DirectedGraph<V,E> dg,
Queue<V> queue)
Creates a new topological order iterator over the directed graph specified, with a
usersupplied queue implementation to allow customized control over tiebreaking in case of
partial order.

Modifier and Type  Method and Description 

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 reencounter a vertex.

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 iterator
next
method. 
finishVertex, getGraph, getSeenData, hasNext, isSeenVertex, next, putSeenData
addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
forEachRemaining
public TopologicalOrderIterator(DirectedGraph<V,E> dg)
dg
 the directed graph to be iterated.public TopologicalOrderIterator(DirectedGraph<V,E> dg, Queue<V> queue)
dg
 the directed graph to be iterated.queue
 queue to use for tiebreak in case of partial order (e.g. a PriorityQueue can be
used to break ties according to vertex priority); must be initially emptyprotected boolean isConnectedComponentExhausted()
CrossComponentIterator
isConnectedComponentExhausted
in class CrossComponentIterator<V,E,Object>
CrossComponentIterator.isConnectedComponentExhausted()
protected void encounterVertex(V vertex, E edge)
CrossComponentIterator
encounterVertex
in class CrossComponentIterator<V,E,Object>
vertex
 the vertex encounterededge
 the edge via which the vertex was encountered, or null if the vertex is a
starting pointCrossComponentIterator.encounterVertex(Object, Object)
protected void encounterVertexAgain(V vertex, E edge)
CrossComponentIterator
encounterVertexAgain
in class CrossComponentIterator<V,E,Object>
vertex
 the vertex reencounterededge
 the edge via which the vertex was reencounteredCrossComponentIterator.encounterVertexAgain(Object, Object)
protected V provideNextVertex()
CrossComponentIterator
next
method.provideNextVertex
in class CrossComponentIterator<V,E,Object>
CrossComponentIterator.provideNextVertex()
Copyright © 2017. All rights reserved.