public class Topological extends Object
Topological
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 depthfirst search. 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 TopologicalX
for a nonrecursive queuebased algorithm
to compute a topological order of a DAG.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and 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 edgeweighted digraph
G has a topological
order and, if so, finds such an order. 
Modifier and Type  Method and Description 

boolean 
hasOrder()
Does the digraph have a topological order?

boolean 
isDAG()
Deprecated.
Replaced by
hasOrder() . 
static void 
main(String[] args)
Unit tests the
Topological 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 Topological(Digraph G)
G
has a topological order and, if so,
finds such a topological order.G
 the digraphpublic Topological(EdgeWeightedDigraph G)
G
has a topological
order and, if so, finds such an order.G
 the edgeweighted 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
otherwise@Deprecated public boolean isDAG()
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
 the 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)
Topological
data type.args
 the commandline arguments