Class TopologicalOrderIterator

  • All Implemented Interfaces:
    java.util.Iterator, GraphIterator

    public class TopologicalOrderIterator
    extends CrossComponentIterator
    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.

    Since:
    Dec 18, 2004
    Author:
    Marden Neubert