Package algs41

# Class EulerianCycle

java.lang.Object
algs41.EulerianCycle

public class EulerianCycle extends Object
The `EulerianCycle` class represents a data type for finding an Eulerian cycle or path in a graph. An Eulerian cycle is a cycle (not necessarily simple) that uses every edge in the graph 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 Θ(E + V) extra space in the worst case (not including the graph).

To compute Eulerian paths in graphs, see `EulerianPath`. To compute Eulerian cycles and paths in digraphs, see `DirectedEulerianCycle` and `DirectedEulerianPath`.

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

Author:
Robert Sedgewick, Kevin Wayne, Nate Liu
• ## Nested Class Summary

Nested Classes
Modifier and Type
Class
Description
`private static class `
`EulerianCycle.Edge`

• ## Field Summary

Fields
Modifier and Type
Field
Description
`private Stack<Integer>`
`cycle`

• ## Constructor Summary

Constructors
Constructor
Description
`EulerianCycle(Graph G)`
Computes an Eulerian cycle in the specified graph, if one exists.
• ## Method Summary

Modifier and Type
Method
Description
`private boolean`
`certifySolution(Graph G)`

`Iterable<Integer>`
`cycle()`
Returns the sequence of vertices on an Eulerian cycle.
`boolean`
`hasEulerianCycle()`
Returns true if the graph has an Eulerian cycle.
`static void`
`main(String[] args)`
Unit tests the `EulerianCycle` data type.
`private static int`
`nonIsolatedVertex(Graph G)`

`private static boolean`
`satisfiesNecessaryAndSufficientConditions(Graph G)`
The code below is solely for testing correctness of the data type.
`private static void`
```unitTest(Graph 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  cycle
• ## Constructor Details

• ### EulerianCycle

public EulerianCycle(Graph G)
Computes an Eulerian cycle in the specified graph, if one exists.
Parameters:
`G` - the graph
• ## Method Details

• ### cycle

public  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 graph has an Eulerian cycle.
Returns:
`true` if the graph has an Eulerian cycle; `false` otherwise
• ### nonIsolatedVertex

private static int nonIsolatedVertex(Graph G)
• ### satisfiesNecessaryAndSufficientConditions

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

private boolean certifySolution(Graph G)
• ### unitTest

private static void unitTest(Graph G, String description)
• ### main

public static void main(String[] args)
Unit tests the `EulerianCycle` data type.
Parameters:
`args` - the command-line arguments