Package com.jgalgo.alg

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:
    Wikipedia

    • Method Detail

      • 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