org._3pq.jgrapht.traverse
Class TopologicalOrderIterator
- GraphIterator, Iterator
public class TopologicalOrderIterator
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.
addTraversalListener , fireConnectedComponentFinished , fireConnectedComponentStarted , fireEdgeTraversed , fireVertexTraversed , isCrossComponentTraversal , isReuseEvents , remove , removeTraversalListener , setCrossComponentTraversal , setReuseEvents |
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.
dg
- the directed graph to be iterated.