Module org.jgrapht.core
Package org.jgrapht.traverse

Class TopologicalOrderIterator<V,E>

java.lang.Object
org.jgrapht.traverse.AbstractGraphIterator<V,E>
org.jgrapht.traverse.TopologicalOrderIterator<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
Iterator<V>, GraphIterator<V,E>
public class TopologicalOrderIterator<V,E> extends AbstractGraphIterator<V,E>
A topological ordering iterator for a directed acyclic graph.

A topological order is a permutation p of the vertices of a graph such that an edge (i,j) implies that i appears before j in p. For more information see wikipedia or wolfram.

The iterator crosses components but does not track them, it only tracks visited vertices. The iterator will detect (at some point) if the graph is not a directed acyclic graph and throw a NotDirectedAcyclicGraphException.

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.

Author:
Marden Neubert, Dimitrios Michail

  • Constructor Details

    • TopologicalOrderIterator

      public TopologicalOrderIterator(Graph<V,E> graph)
      Construct a topological order iterator.

      Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html. In case of partial order, tie-breaking is arbitrary.

      Parameters:
      graph - the directed graph to be iterated

    • TopologicalOrderIterator

      public TopologicalOrderIterator(Graph<V,E> graph, Comparator<V> comparator)
      Construct a topological order iterator.

      Traversal will start at one of the graph's sources. See the definition of source at http://mathworld.wolfram.com/Source.html. In case of partial order, a comparator is used to break ties.

      Parameters:
      graph - the directed graph to be iterated
      comparator - comparator in order to break ties in case of partial order
      Throws:
      NotDirectedAcyclicGraphException - if graph is not a DAG

  • Method Details

    • isCrossComponentTraversal

      public boolean isCrossComponentTraversal()
      Description copied from class: AbstractGraphIterator
      Test whether this iterator is set to traverse the graph across connected components.
      Specified by:
      isCrossComponentTraversal in interface GraphIterator<V,E>
      Overrides:
      isCrossComponentTraversal in class AbstractGraphIterator<V,E>
      Returns:
      true always, since this iterator does not care about components

    • setCrossComponentTraversal

      public void setCrossComponentTraversal(boolean crossComponentTraversal)
      Description copied from class: AbstractGraphIterator
      Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.
      Overrides:
      setCrossComponentTraversal in class AbstractGraphIterator<V,E>
      Parameters:
      crossComponentTraversal - if true traverses across connected components.
      Throws:
      IllegalArgumentException - if disabling the cross components nature of this iterator is attempted

    • hasNext

      public boolean hasNext()

    • next

      public V next()