Class DirectedCycle

java.lang.Object

DirectedCycle

public class DirectedCycle
extends java.lang.Object

The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle. The hasCycle operation determines whether the digraph has a directed cycle and, and of so, the cycle 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 hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.

See Topological to compute a topological order if the digraph is acyclic.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
DirectedCycle(Digraph G) Determines whether the digraph G has a directed cycle and, if so, finds such a cycle.

Method Summary

Methods

Modifier and Type	Method and Description
java.lang.Iterable<java.lang.Integer>	cycle() Returns a directed cycle if the digraph has a directed cycle, and null otherwise.
boolean	hasCycle() Does the digraph have a directed cycle?
static void	main(java.lang.String[] args) Unit tests the DirectedCycle data type.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DirectedCycle

public DirectedCycle(Digraph G)

Determines whether the digraph G has a directed cycle and, if so, finds such a cycle.

Parameters:

G - the digraph

Method Detail

hasCycle

public boolean hasCycle()

Does the digraph have a directed cycle?

Returns:

true if the digraph has a directed cycle, false otherwise

cycle

public java.lang.Iterable<java.lang.Integer> cycle()

Returns a directed cycle if the digraph has a directed cycle, and null otherwise.

Returns:

a directed cycle (as an iterable) if the digraph has a directed cycle, and null otherwise

main

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

Unit tests the DirectedCycle data type.