Class TopologicalOrderIterator<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    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 KosarajuStrongConnectivityInspector.

    Since:
    Dec 18, 2004
    • Field Detail

      • queue

        private java.util.Queue<V> queue
    • Constructor Detail

      • TopologicalOrderIterator

        public 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. Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html.
        Parameters:
        dg - the directed graph to be iterated.
      • TopologicalOrderIterator

        public 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. Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html.
        Parameters:
        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 empty
      • TopologicalOrderIterator

        private TopologicalOrderIterator​(DirectedGraph<V,​E> dg,
                                         V start)