Class UnitWeightedTopologicalNumbering


public class UnitWeightedTopologicalNumbering
extends AbstractTopologicalSort

This algorithm class computes the optimal unit-weighted topological numbering for a given DAG. Each Vertex is assigned a non-unique order-number. The number of a given Vertex is equal to 1 plus the highest value of any of its predecessors' numbers. The order-number of a Vertex may be retrieved using the number(Vertex) method.

$Revision: 1.5 $, $Date: 1999/08/31 02:27:08 $
Natasha Gelfand (ng), Lucy Perry (lep)
See Also:

Fields inherited from class jdsl.graph.algo.AbstractTopologicalSort
graph_, is_cyclic_, NUMBER_KEY_, queue_
Constructor Summary
Method Summary
protected  void sort()
          The meat of the algorithm.
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


public UnitWeightedTopologicalNumbering()
Method Detail


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 non-unique 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.
sort in class AbstractTopologicalSort
Following copied from class: jdsl.graph.algo.AbstractTopologicalSort
See Also:
TopologicalSort, UnitWeightedTopologicalNumbering