Package org.jgrapht.traverse

Class TopologicalOrderIterator<V,E>

java.lang.Object
org.jgrapht.traverse.AbstractGraphIterator<V,E>
org.jgrapht.traverse.CrossComponentIterator<V,E,Object>
org.jgrapht.traverse.TopologicalOrderIterator<V,E>
All Implemented Interfaces:
Iterator<V>, GraphIterator<V,E>
public class TopologicalOrderIterator<V,E> extends CrossComponentIterator<V,E,Object>
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.

Since:
Dec 18, 2004
Author:
Marden Neubert