Package org.jgrapht.alg.cycle

Class HierholzerEulerianCycle<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    EulerianCycleAlgorithm<V,​E>
    public class HierholzerEulerianCycle<V,​E>
extends java.lang.Object
implements EulerianCycleAlgorithm<V,​E>
    An implementation of Hierholzer's algorithm for finding an Eulerian cycle in Eulerian graphs. The algorithm works with directed and undirected graphs which may contain loops and/or multiple (parallel) edges. The running time is linear, i.e. $O(|E|)$ where $|E|$ is the cardinality of the edge set of the graph.

    See the Wikipedia article for details and references about Eulerian cycles and a short description of Hierholzer's algorithm for the construction of an Eulerian cycle. The original presentation of the algorithm dates back to 1873 and the following paper: Carl Hierholzer: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6(1), 30–32, 1873.

    Author:
    Dimitrios Michail

    • Constructor Detail

      • HierholzerEulerianCycle

        public HierholzerEulerianCycle()

    • Method Detail

      • isEulerian

        public boolean isEulerian​(Graph<V,​E> graph)
        Test whether a graph is Eulerian. An Eulerian graph is a graph containing an Eulerian cycle.
        Parameters:
        graph - the input graph
        Returns:
        true if the graph is Eulerian, false otherwise

      • getEulerianCycle

        public GraphPath<V,​E> getEulerianCycle​(Graph<V,​E> g)
        Compute an Eulerian cycle of a graph.
        Specified by:
        getEulerianCycle in interface EulerianCycleAlgorithm<V,​E>
        Parameters:
        g - the input graph
        Returns:
        an Eulerian cycle
        Throws:
        java.lang.IllegalArgumentException - in case the graph is not Eulerian

      • initialize

        protected void initialize​(Graph<V,​E> g)
        Index the graph and create a double-linked list representation suitable for vertex and edge removals in constant time. Ignore any vertices with zero degrees.
        Parameters:
        g - the graph to index

      • cleanup

        protected void cleanup()
        Release any memory held.

      • computePartialCycle

        protected Pair<HierholzerEulerianCycle.EdgeNode,​HierholzerEulerianCycle.EdgeNode> computePartialCycle()
        Computes a partial cycle assuming that all vertices have an even degree. The partial cycle always begin from the first graph vertex in the vertex list.
        Returns:
        the partial's cycle head and tail nodes as a pair

      • updateGraphAndInsertLocations

        protected void updateGraphAndInsertLocations​(Pair<HierholzerEulerianCycle.EdgeNode,​HierholzerEulerianCycle.EdgeNode> partialCycle,
                                             HierholzerEulerianCycle.VertexNode partialCycleSourceVertex)
        Iterate over the partial cycle to remove vertices with zero degrees and compute new insert locations for vertices with non-zero degrees. It is important to move vertices with new insert locations to the front of the vertex list, in order to make sure that we always start partial cycles from already visited vertices.
        Parameters:
        partialCycle - the partial cycle
        partialCycleSourceVertex - the source vertex of the first edge in the partial cycle

      • buildWalk

        protected GraphWalk<V,​E> buildWalk()
        Build final walk
        Returns:
        the final walk

      • moveToFront

        protected void moveToFront​(HierholzerEulerianCycle.VertexNode vNode)
        Move a vertex as first in the vertex list.
        Parameters:
        vNode - vertex to move to front

      • unlink

        protected void unlink​(HierholzerEulerianCycle.EdgeNode eNode)
        Unlink an edge from the adjacency lists of its end-points.
        Parameters:
        eNode - edge to unlink