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 IllegalArgumentException.

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:

December 2004

Author:

Marden Neubert, Dimitrios Michail

Field Summary

Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator

crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
boolean	hasNext()
boolean	isCrossComponentTraversal() Test whether this iterator is set to traverse the graph across connected components.
V	next()
void	setCrossComponentTraversal(boolean crossComponentTraversal) Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.

Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator

addTraversalListener, createEdgeTraversalEvent, createVertexTraversalEvent, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, getGraph, isReuseEvents, remove, removeTraversalListener, setReuseEvents

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Iterator

forEachRemaining

Constructor Detail

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

Method Detail

isCrossComponentTraversal

public boolean isCrossComponentTraversal()

Test whether this iterator is set to traverse the graph across connected components. Always returns true since the iterator does not care about components.

Specified by:

isCrossComponentTraversal in interface GraphIterator<V,E>

Overrides:

isCrossComponentTraversal in class AbstractGraphIterator<V,E>

Returns:

true if traverses across connected components, otherwise false.

setCrossComponentTraversal

public void setCrossComponentTraversal(boolean crossComponentTraversal)

Sets the cross component traversal flag - indicates whether to traverse the graph across connected components. Trying to disable the cross components nature of this iterator will result into throwing a IllegalArgumentException.

Overrides:

setCrossComponentTraversal in class AbstractGraphIterator<V,E>

Parameters:

crossComponentTraversal - if true traverses across connected components.

hasNext

public boolean hasNext()

next

public V next()