## 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). 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 Θ(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).

See `DirectedCycle`, `DirectedCycleX`, and `EdgeWeightedDirectedCycle` for computing a directed cycle if the digraph is not a DAG. See `TopologicalX` for a nonrecursive queue-based algorithm for computing 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 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

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

`clone, equals, 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 topological order, and `null` otherwise.
Returns:
a topological order of the vertices (as an iterable) 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
• #### rank

`public int rank​(int v)`
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