org._3pq.jgrapht.traverse

Class TopologicalOrderIterator

Implemented Interfaces:
GraphIterator, Iterator

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.

Author:
Marden Neubert
Since:
Dec 18, 2004

Constructor Summary

TopologicalOrderIterator(DirectedGraph dg)
Creates a new topological order iterator over the directed graph specified.

Method Summary

protected void
encounterVertex(Object vertex, Edge edge)
protected void
encounterVertexAgain(Object vertex, Edge edge)
protected boolean
isConnectedComponentExhausted()
protected Object
provideNextVertex()

Methods inherited from class org._3pq.jgrapht.traverse.CrossComponentIterator

encounterVertex, encounterVertexAgain, getSeenData, hasNext, isConnectedComponentExhausted, isSeenVertex, next, provideNextVertex, putSeenData

Methods inherited from class org._3pq.jgrapht.traverse.AbstractGraphIterator

addTraversalListener, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents

Constructor Details

TopologicalOrderIterator

public TopologicalOrderIterator(DirectedGraph dg)
Creates a new topological order iterator over the directed graph specified. Traversal will start at one of the graphs sources. See the definition of source at http://mathworld.wolfram.com/Source.html.
Parameters:
dg - the directed graph to be iterated.

Method Details

encounterVertex

protected void encounterVertex(Object vertex,
                               Edge edge)
Overrides:
encounterVertex in interface CrossComponentIterator

encounterVertexAgain

protected void encounterVertexAgain(Object vertex,
                                    Edge edge)
Overrides:
encounterVertexAgain in interface CrossComponentIterator

isConnectedComponentExhausted

protected boolean isConnectedComponentExhausted()
Overrides:
isConnectedComponentExhausted in interface CrossComponentIterator

provideNextVertex

protected Object provideNextVertex()
Overrides:
provideNextVertex in interface CrossComponentIterator