edu.princeton.cs.algs4

Class Topological

java.lang.Object

edu.princeton.cs.algs4.Topological

public class Topological
extends java.lang.Object

The 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 depth-first 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 queue-based 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 Summary

Constructors

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 edge-weighted digraph G has a topological order and, if so, finds such an order.

Method Summary

Modifier and Type	Method and Description
boolean	hasOrder() Does the digraph have a topological order?
boolean	isDAG() Deprecated. Replaced by hasOrder().
static void	main(java.lang.String[] args) Unit tests the Topological 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

Topological

public Topological(Digraph G)

Determines whether the digraph G has a topological order and, if so, finds such a topological order.

Parameters:

G - the digraph

Topological

public Topological(EdgeWeightedDigraph G)

Determines whether the edge-weighted digraph G has a topological order and, if so, finds such an order.

Parameters:

G - the edge-weighted 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

isDAG

@Deprecated
public boolean isDAG()

Deprecated. Replaced by 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 - the 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 Topological data type.

Parameters:

args - the command-line arguments