jdsl.graph.algo
Class UnitWeightedTopologicalNumbering

java.lang.Object
  |
  +--jdsl.graph.algo.AbstractTopologicalSort
        |
        +--jdsl.graph.algo.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.

Version:

$Revision: 1.5 $, $Date: 1999/08/31 02:27:08 $

Author:

Natasha Gelfand (ng), Lucy Perry (lep)

See Also:

AbstractTopologicalSort

Fields inherited from class jdsl.graph.algo.AbstractTopologicalSort

graph_, is_cyclic_, NUMBER_KEY_, queue_

Constructor Summary

UnitWeightedTopologicalNumbering()
Constructor

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

UnitWeightedTopologicalNumbering

public UnitWeightedTopologicalNumbering()

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 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.

Overrides:

sort in class AbstractTopologicalSort

Following copied from class: jdsl.graph.algo.AbstractTopologicalSort

See Also:

TopologicalSort, UnitWeightedTopologicalNumbering