public class Topological extends java.lang.Object
This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasOrder operation takes constant time; the order operation takes time proportional to V.
See DirectedCycle
and EdgeWeightedDirectedCycle
to compute a
directed cycle if the digraph is not a DAG.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
Topological(Digraph G)
Determines whether the digraph G has a topological order and, if so,
finds such a topological order.
|
Topological(EdgeWeightedDigraph G)
Determines whether the edge-weighted digraph G has a topological
order and, if so, finds such an order.
|
Modifier and Type | Method and Description |
---|---|
boolean |
hasOrder()
Does the digraph have a topological order?
|
static void |
main(java.lang.String[] args)
Unit tests the Topological data type.
|
java.lang.Iterable<java.lang.Integer> |
order()
Returns a topological order if the digraph has a topologial order,
and null otherwise.
|
public Topological(Digraph G)
G
- the digraphpublic Topological(EdgeWeightedDigraph G)
G
- the edge-weighted digraphpublic java.lang.Iterable<java.lang.Integer> order()
public boolean hasOrder()
public static void main(java.lang.String[] args)