edu.princeton.cs.algs4

## Class TopologicalX

• Object
• edu.princeton.cs.algs4.TopologicalX

• ```public class TopologicalX
extends Object```
The `TopologicalX` 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 a nonrecursive, queue-based algorithm. 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` to compute a directed cycle if the digraph is not a DAG. See `Topological` for a recursive version that uses depth-first search.

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
`TopologicalX(Digraph G)`
Determines whether the digraph `G` has a topological order and, if so, finds such a topological order.
`TopologicalX(EdgeWeightedDigraph G)`
Determines whether the edge-weighted digraph `G` has a topological order and, if so, finds such a topological order.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`boolean` `hasOrder()`
Does the digraph have a topological order?
`static void` `main(String[] args)`
Unit tests the `TopologicalX` 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

• #### TopologicalX

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

`public TopologicalX(EdgeWeightedDigraph G)`
Determines whether the edge-weighted digraph `G` has a topological order and, if so, finds such a topological order.
Parameters:
`G` - the 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
• #### 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` - 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 `TopologicalX` data type.
Parameters:
`args` - the command-line arguments