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:
- JDSL 2.1.1
- Author:
- Natasha Gelfand (ng), Lucy Perry (lep)
- See Also:
AbstractTopologicalSort
Method Summary |
protected void |
sort()
The meat of the algorithm. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
UnitWeightedTopologicalNumbering
public UnitWeightedTopologicalNumbering()
- Constructor
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.
- Specified by:
sort
in class AbstractTopologicalSort
- See Also:
TopologicalSort
,
UnitWeightedTopologicalNumbering