|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.jgrapht.traverse.AbstractGraphIterator<V,E>
org.jgrapht.traverse.CrossComponentIterator<V,E,java.lang.Object>
org.jgrapht.traverse.TopologicalOrderIterator<V,E>
public class TopologicalOrderIterator<V,E>
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
or StrongConnectivityInspector
.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class org.jgrapht.traverse.CrossComponentIterator |
---|
CrossComponentIterator.VisitColor |
Field Summary |
---|
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator |
---|
nListeners |
Constructor Summary | |
---|---|
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. |
Method Summary | |
---|---|
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. |
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. |
Methods inherited from class org.jgrapht.traverse.CrossComponentIterator |
---|
finishVertex, getGraph, getSeenData, hasNext, isSeenVertex, next, putSeenData |
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator |
---|
addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public TopologicalOrderIterator(DirectedGraph<V,E> dg)
dg
- the directed graph to be iterated.public TopologicalOrderIterator(DirectedGraph<V,E> dg, java.util.Queue<V> queue)
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 emptyMethod Detail |
---|
protected boolean isConnectedComponentExhausted()
CrossComponentIterator
isConnectedComponentExhausted
in class CrossComponentIterator<V,E,java.lang.Object>
CrossComponentIterator.isConnectedComponentExhausted()
protected void encounterVertex(V vertex, E edge)
CrossComponentIterator
encounterVertex
in class CrossComponentIterator<V,E,java.lang.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,java.lang.Object>
vertex
- the vertex re-encounterededge
- the edge via which the vertex was re-encounteredCrossComponentIterator.encounterVertexAgain(Object, Object)
protected V provideNextVertex()
CrossComponentIterator
next
method.
provideNextVertex
in class CrossComponentIterator<V,E,java.lang.Object>
CrossComponentIterator.provideNextVertex()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |