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:
- JDSL 2.1.1
- Author:
- Lucy Perry (lep)
- See Also:
AbstractTopologicalSort
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 java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
TopologicalSort
public TopologicalSort()
- 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 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.
- Specified by:
sort
in class 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.