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.