edu.princeton.cs.algs4

Class Topological

• Object
• edu.princeton.cs.algs4.Topological

• ```public class Topological
extends Object```
The `Topological` class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The hasOrder operation determines whether the digraph has a topological order, and if so, the order operation returns one.

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 and rank operations takes constant time; the order operation takes time proportional to V.

See `DirectedCycle`, `DirectedCycleX`, and `EdgeWeightedDirectedCycle` to compute a directed cycle if the digraph is not a DAG. See `TopologicalX` for a nonrecursive queue-based algorithm to compute a topological order of a DAG.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• Constructor Summary

Constructors
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.
• Method Summary

Methods
Modifier and Type Method and Description
`boolean` `hasOrder()`
Does the digraph have a topological order?
`boolean` `isDAG()`
Deprecated.
`static void` `main(String[] args)`
Unit tests the `Topological` data type.
`Iterable<Integer>` `order()`
Returns a topological order if the digraph has a topologial order, and `null` otherwise.
`int` `rank(int v)`
The the rank of vertex `v` in the topological order; -1 if the digraph is not a DAG
• Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Constructor Detail

• Topological

`public Topological(Digraph G)`
Determines whether the digraph `G` has a topological order and, if so, finds such a topological order.
Parameters:
`G` - the digraph
• Topological

`public Topological(EdgeWeightedDigraph G)`
Determines whether the edge-weighted digraph `G` has a topological order and, if so, finds such an order.
Parameters:
`G` - the edge-weighted digraph
• Method Detail

• order

`public Iterable<Integer> order()`
Returns a topological order if the digraph has a topologial order, and `null` otherwise.
Returns:
a topological order of the vertices (as an interable) if the digraph has a topological order (or equivalently, if the digraph is a DAG), and `null` otherwise
• hasOrder

`public boolean hasOrder()`
Does the digraph have a topological order?
Returns:
`true` if the digraph has a topological order (or equivalently, if the digraph is a DAG), and `false` otherwise
• isDAG

```@Deprecated
public boolean isDAG()```
Deprecated. Replaced by `hasOrder()`.
Does the digraph have a topological order?
Returns:
`true` if the digraph has a topological order (or equivalently, if the digraph is a DAG), and `false` otherwise
• rank

`public int rank(int v)`
The the rank of vertex `v` in the topological order; -1 if the digraph is not a DAG
Parameters:
`v` - the vertex
Returns:
the position of vertex `v` in a topological order of the digraph; -1 if the digraph is not a DAG
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• main

`public static void main(String[] args)`
Unit tests the `Topological` data type.
Parameters:
`args` - the command-line arguments