Package com.jgalgo.alg.euler

Interface EulerianTourAlgo

public interface EulerianTourAlgo
Eulerian tour calculation algorithm.

An Eulerian tour is a tour that visits every edge exactly once (allowing for revisiting vertices). For a connected undirected graph, if all vertices have an even degree, an Eulerian cycle will be found. If exactly two vertices have an odd degree, called \(s,t\), an Eulerian tour that start at \(s\) and ends at \(t\) exists. For any other vertices degrees an Eulerian tour does not exists. For a strongly connected directed graph, the in-degree and out-degree of each vertex must be equal for an Eulerian cycle to exists. If exactly one vertex \(s\) has one more out-edge than in-edges, and one vertex \(t\) has one more in-edge than out-edges, an Eulerian tour that start at \(s\) and ends at \(t\) exists.

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    default <V, E> Path<V,E>
    computeEulerianTour(Graph<V,E> g)
    Compute an Eulerian tour in the graph that visit all edges exactly once.
    <V, E> Optional<Path<V,E>>
    computeEulerianTourIfExist(Graph<V,E> g)
    Compute an Eulerian tour in the graph that visit all edges exactly once if one exists.
    default <V, E> boolean
    isEulerian(Graph<V,E> g)
    Check whether a graph is Eulerian.
    static <V, E> boolean
    isEulerianTour(Graph<V,E> g, List<E> tour)
    Check if the given tour is an Eulerian tour in the given graph.
    static EulerianTourAlgo
    newInstance()
    Create a new Eulerian tour computation algorithm.

  • Method Details

    • computeEulerianTour

      default <V, E> Path<V,E> computeEulerianTour(Graph<V,E> g)
      Compute an Eulerian tour in the graph that visit all edges exactly once.

      The graph is assumed to be (strongly) connected. Either a cycle or tour will be found, depending on the vertices degrees.

      If g is IntGraph, the returned object is IPath.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      an Eulerian tour that visit all edges of the graph exactly once
      Throws:
      IllegalArgumentException - if there is no Eulerian tour in the graph

    • computeEulerianTourIfExist

      <V, E> Optional<Path<V,E>> computeEulerianTourIfExist(Graph<V,E> g)
      Compute an Eulerian tour in the graph that visit all edges exactly once if one exists.

      The graph is assumed to be (strongly) connected. Either a cycle or tour will be found, depending on the vertices degrees.

      If g is IntGraph, the returned optional will contain IPath.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      an Eulerian tour that visit all edges of the graph exactly once if one exists

    • isEulerian

      default <V, E> boolean isEulerian(Graph<V,E> g)
      Check whether a graph is Eulerian.

      A graph is Eulerian if it contains an Eulerian tour.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      true if the graph is Eulerian, false otherwise

    • isEulerianTour

      static <V, E> boolean isEulerianTour(Graph<V,E> g, List<E> tour)
      Check if the given tour is an Eulerian tour in the given graph.

      A list of edges form an Eulerian tour in a graph if it firstly is a valid path in the graph, and it visit all edges of the graph exactly once.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      tour - a list of edges that should form an Eulerian tour in the graph
      Returns:
      true if the given tour is an Eulerian tour in the given graph, false otherwise

    • newInstance

      static EulerianTourAlgo newInstance()
      Create a new Eulerian tour computation algorithm.

      This is the recommended way to instantiate a new EulerianTourAlgo object.

      Returns:
      a default implementation of EulerianTourAlgo