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 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.

    Since:
    October 2016