Class EdgeWeightedDirectedCycle

java.lang.Object

EdgeWeightedDirectedCycle

public class EdgeWeightedDirectedCycle
extends java.lang.Object

The EdgeWeightedDirectedCycle class represents a data type for determining whether an edge-weighted digraph has a directed cycle. The hasCycle operation determines whether the edge-weighted digraph has a directed cycle and, if 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 edge-weighted digraph is acyclic.

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

Constructor Summary

Constructors

Constructor and Description
EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) Determines whether the edge-weighted 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<DirectedEdge>	cycle() Returns a directed cycle if the edge-weighted digraph has a directed cycle, and null otherwise.
boolean	hasCycle() Does the edge-weighted digraph have a directed cycle?
static void	main(java.lang.String[] args) Unit tests the EdgeWeightedDirectedCycle data type.

Methods inherited from class java.lang.Object

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

Constructor Detail

EdgeWeightedDirectedCycle

public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G)

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

Parameters:

G - the edge-weighted digraph

Method Detail

hasCycle

public boolean hasCycle()

Does the edge-weighted digraph have a directed cycle?

Returns:

true if the edge-weighted digraph has a directed cycle, false otherwise

cycle

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

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

Returns:

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

main

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

Unit tests the EdgeWeightedDirectedCycle data type.