edu.princeton.cs.algs4

Class Topological

Object

edu.princeton.cs.algs4.Topological

public class Topological
extends Object

The Topological 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 depth-first search. 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, and EdgeWeightedDirectedCycle for computing a directed cycle if the digraph is not a DAG. See TopologicalX for a nonrecursive queue-based algorithm for computing a topological order of a DAG.

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 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(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

Methods inherited from class Object

clone, equals, finalize, 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 Iterable<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:

IllegalArgumentException - unless 0 <= v < V

main

public static void main(String[] args)

Unit tests the Topological data type.

Parameters:

args - the command-line arguments