Package algs42

Class DirectedEulerianPath

java.lang.Object
algs42.DirectedEulerianPath
public class DirectedEulerianPath extends Object
The DirectedEulerianPath class represents a data type for finding an Eulerian path in a digraph. An Eulerian path is a path (not necessarily simple) that uses every edge in the digraph exactly once.

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

To compute Eulerian cycles in digraphs, see DirectedEulerianCycle. 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 Details

  • Constructor Details

    • DirectedEulerianPath

      public DirectedEulerianPath(Digraph G)
      Computes an Eulerian path in the specified digraph, if one exists.
      Parameters:
      G - the digraph

  • Method Details

    • path

      public Iterable<Integer> path()
      Returns the sequence of vertices on an Eulerian path.
      Returns:
      the sequence of vertices on an Eulerian path; null if no such path

    • hasEulerianPath

      public boolean hasEulerianPath()
      Returns true if the digraph has an Eulerian path.
      Returns:
      true if the digraph has an Eulerian path; 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.

    • check

      private boolean check(Digraph G)

    • unitTest

      private static void unitTest(Digraph G, String description)

    • main

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