Package algs42

Class DirectedEulerianCycle

java.lang.Object

algs42.DirectedEulerianCycle

public class DirectedEulerianCycle
extends Object

The DirectedEulerianCycle class represents a data type for finding an Eulerian cycle or path in a digraph. An Eulerian cycle is a cycle (not necessarily simple) that uses every edge in the digraph exactly once.

This implementation uses a nonrecursive depth-first search. The constructor takes Θ(E + V) time in the worst case, where E is the number of edges and V is the number of vertices Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).

To compute Eulerian paths in digraphs, see DirectedEulerianPath. To compute Eulerian cycles and paths in undirected graphs, see EulerianCycle and EulerianPath.

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

Author:

Robert Sedgewick, Kevin Wayne, Nate Liu

Field Summary

Fields

Modifier and Type	Field	Description
private Stack<Integer>	cycle

Constructor Summary

Constructors

Constructor	Description
DirectedEulerianCycle(Digraph G)	Computes an Eulerian cycle in the specified digraph, if one exists.

Method Summary

Modifier and Type	Method	Description
private boolean	certifySolution(Digraph G)
Iterable<Integer>	cycle()	Returns the sequence of vertices on an Eulerian cycle.
boolean	hasEulerianCycle()	Returns true if the digraph has an Eulerian cycle.
static void	main(String[] args)	Unit tests the DirectedEulerianCycle data type.
private static int	nonIsolatedVertex(Digraph G)
private static boolean	satisfiesNecessaryAndSufficientConditions(Digraph G)	The code below is solely for testing correctness of the data type.
private static void	unitTest(Digraph G, String description)

Methods inherited from class java.lang.Object

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

Field Details

cycle

private Stack<Integer> cycle

Constructor Details

DirectedEulerianCycle

public DirectedEulerianCycle(Digraph G)

Computes an Eulerian cycle in the specified digraph, if one exists.

Parameters:

G - the digraph

Method Details

cycle

public Iterable<Integer> cycle()

Returns the sequence of vertices on an Eulerian cycle.

Returns:

the sequence of vertices on an Eulerian cycle; null if no such cycle

hasEulerianCycle

public boolean hasEulerianCycle()

Returns true if the digraph has an Eulerian cycle.

Returns:

true if the digraph has an Eulerian cycle; false otherwise

nonIsolatedVertex

private static int nonIsolatedVertex(Digraph G)

satisfiesNecessaryAndSufficientConditions

private static boolean satisfiesNecessaryAndSufficientConditions(Digraph G)

The code below is solely for testing correctness of the data type.

certifySolution

private boolean certifySolution(Digraph G)

unitTest

private static void unitTest(Digraph G,
 String description)

main

public static void main(String[] args)

Unit tests the DirectedEulerianCycle data type.

Parameters:

args - the command-line arguments