jdsl.graph.algo
Class TopologicalSort

java.lang.Object
  |
  +--jdsl.graph.algo.AbstractTopologicalSort
        |
        +--jdsl.graph.algo.TopologicalSort

public class TopologicalSort
extends AbstractTopologicalSort

This algorithm class performs a topological ordering on a given DAG. Each Vertex is labeled with a unique order-number which may be retrieved using the number(Vertex) method. In addition to the number(Vertex) query method, this algo-object provides a method sortedVertices(), for obtaining a VertexIterator containing the Vertices in topologically sorted order.

Version:
$Revision: 1.12 $, $Date: 1999/08/31 21:07:40 $
Author:
Lucy Perry (lep)
See Also:
AbstractTopologicalSort

Fields inherited from class jdsl.graph.algo.AbstractTopologicalSort
graph_, is_cyclic_, NUMBER_KEY_, queue_
 
Constructor Summary
TopologicalSort()
          Constructor
 
Method Summary
protected  void sort()
          The meat of the algorithm.
 VertexIterator sortedVertices()
          Returns a VertexIterator containing all the Vertices in topologically sorted order.
 
Methods inherited from class jdsl.graph.algo.AbstractTopologicalSort
cleanup, execute, init, isCyclic, number
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

TopologicalSort

public TopologicalSort()
Constructor
Method Detail

sort

protected final void sort()
The meat of the algorithm. This method is called from the superclass's execute(.) method. If the Graph is acyclic, then the algorithm labels each Vertex with a unique topological order-number. If the Graph contains cycles, then some Vertices will not be visited, and the is_cyclic_ boolean will be set to true. Takes O(V+E) time, where V = number of Vertices in the Graph, and E = number of Edges, because the algorithm traverses all the outgoing edges of each visited Vertex exactly once.
Overrides:
sort in class AbstractTopologicalSort
Following copied from class: jdsl.graph.algo.AbstractTopologicalSort
See Also:
TopologicalSort, UnitWeightedTopologicalNumbering

sortedVertices

public VertexIterator sortedVertices()
                              throws InvalidQueryException
Returns a VertexIterator containing all the Vertices in topologically sorted order. Takes O(1) time.
Returns:
VertexIterator
Throws:
InvalidQueryException - if the Graph has cycles, or if the algorithm has not yet been executed.