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 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 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 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

• 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 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` - 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