edu.princeton.cs.algorithms

Class Topological

java.lang.Object

edu.princeton.cs.algorithms.Topological

public class Topological
extends 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 operation takes constant time; the order operation takes time proportional to V.

See DirectedCycle and EdgeWeightedDirectedCycle to compute a directed cycle if the digraph is not 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?
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.

Methods inherited from class java.lang.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

main

public static void main(String[] args)

Unit tests the Topological data type.