Logo Search packages:      
Sourcecode: libjgrapht-java version File versions  Download package

org::_3pq::jgrapht::traverse::TopologicalOrderIterator Class Reference

Inheritance diagram for org::_3pq::jgrapht::traverse::TopologicalOrderIterator:

org::_3pq::jgrapht::traverse::CrossComponentIterator org::_3pq::jgrapht::traverse::AbstractGraphIterator org::_3pq::jgrapht::traverse::GraphIterator

List of all members.


Detailed Description

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

Definition at line 77 of file TopologicalOrderIterator.java.


Public Member Functions

void addTraversalListener (TraversalListener l)
boolean hasNext ()
boolean isCrossComponentTraversal ()
boolean isReuseEvents ()
Object next ()
void remove ()
void removeTraversalListener (TraversalListener l)
void setCrossComponentTraversal (boolean crossComponentTraversal)
void setReuseEvents (boolean reuseEvents)
 TopologicalOrderIterator (DirectedGraph dg)

Protected Member Functions

void encounterVertex (Object vertex, Edge edge)
void encounterVertexAgain (Object vertex, Edge edge)
void fireConnectedComponentFinished (ConnectedComponentTraversalEvent e)
void fireConnectedComponentStarted (ConnectedComponentTraversalEvent e)
void fireEdgeTraversed (EdgeTraversalEvent e)
void fireVertexTraversed (VertexTraversalEvent e)
Object getSeenData (Object vertex)
boolean isConnectedComponentExhausted ()
boolean isSeenVertex (Object vertex)
Object provideNextVertex ()
Object putSeenData (Object vertex, Object data)

Static Package Functions

static Specifics createGraphSpecifics (Graph g)

Private Member Functions

void decrementInDegree (Object vertex)
 TopologicalOrderIterator (DirectedGraph dg, Object start)
 TopologicalOrderIterator (DirectedGraph dg, LinkedList queue, Map inDegreeMap)

Static Private Member Functions

static Object initialize (DirectedGraph dg, LinkedList queue, Map inDegreeMap)

Private Attributes

Map m_inDegreeMap
LinkedList m_queue

The documentation for this class was generated from the following file:

Generated by  Doxygen 1.6.0   Back to index