Package edu.princeton.cs.algs4
Class TopologicalX
 Object

 edu.princeton.cs.algs4.TopologicalX

public class TopologicalX extends Object
TheTopologicalX
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, queuebased 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
, andEdgeWeightedDirectedCycle
to compute a directed cycle if the digraph is not a DAG. SeeTopological
for a recursive version that uses depthfirst 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 digraphG
has a topological order and, if so, finds such a topological order.TopologicalX(EdgeWeightedDigraph G)
Determines whether the edgeweighted digraphG
has a topological order and, if so, finds such a topological order.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
hasOrder()
Does the digraph have a topological order?static void
main(String[] args)
Unit tests theTopologicalX
data type.Iterable<Integer>
order()
Returns a topological order if the digraph has a topological order, andnull
otherwise.int
rank(int v)
The rank of vertexv
in the topological order; 1 if the digraph is not a DAG



Constructor Detail

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

TopologicalX
public TopologicalX(EdgeWeightedDigraph G)
Determines whether the edgeweighted digraphG
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, andnull
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), andfalse
otherwise

rank
public int rank(int v)
The rank of vertexv
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
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theTopologicalX
data type. Parameters:
args
 the commandline arguments

