Class TopologicalOrderIterator<V,​E>

  • All Implemented Interfaces:
    java.util.Iterator<V>, GraphIterator<V,​E>

    public class TopologicalOrderIterator<V,​E>
    extends CrossComponentIterator<V,​E,​java.lang.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