org.jgrapht.alg.cycle

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

Constructors

Constructor and Description
HierholzerEulerianCycle()

Method Summary

Modifier and Type	Method and Description
GraphPath<V,E>	getEulerianCycle(Graph<V,E> g) Compute an Eulerian cycle of a graph.
boolean	isEulerian(Graph<V,E> graph) Test whether a graph is Eulerian.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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:

IllegalArgumentException - in case the graph is not Eulerian