public class TopologicalX extends Object
TopologicalX
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 a nonrecursive, queuebased algorithm. 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 Topological
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.
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 edgeweighted digraph
G has a
topological order and, if so, finds such a topological order. 
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 
public TopologicalX(Digraph G)
G
has a topological order and, if so,
finds such a topological order.G
 the digraphpublic TopologicalX(EdgeWeightedDigraph G)
G
has a
topological order and, if so, finds such a topological order.G
 the digraphpublic Iterable<Integer> order()
null
otherwise.null
otherwisepublic boolean hasOrder()
true
if the digraph has a topological order (or equivalently,
if the digraph is a DAG), and false
otherwisepublic int rank(int v)
v
in the topological order;
1 if the digraph is not a DAGv
 vertexv
in a topological order
of the digraph; 1 if the digraph is not a DAGIllegalArgumentException
 unless 0 <= v < V
public static void main(String[] args)
TopologicalX
data type.args
 the commandline arguments