edu.princeton.cs.algs4

Class TopologicalX

java.lang.Object

edu.princeton.cs.algs4.TopologicalX

public class TopologicalX
extends java.lang.Object

The 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, queue-based 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 depth-first search.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and 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

Modifier and Type	Method and Description
boolean	hasOrder() Does the digraph have a topological order?
static void	main(java.lang.String[] args) Unit tests the TopologicalX data type.
java.lang.Iterable<java.lang.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 java.lang.Object

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 java.lang.Iterable<java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

main

public static void main(java.lang.String[] args)

Unit tests the TopologicalX data type.

Parameters:

args - the command-line arguments