Class HierholzerEulerianCycle<V,​E>

java.lang.Object
org.jgrapht.alg.cycle.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