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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	HierholzerEulerianCycle.EdgeNode
protected class	HierholzerEulerianCycle.VertexNode

Field Summary

Fields

Modifier and Type	Field and Description
protected HierholzerEulerianCycle.EdgeNode	eulerianHead
protected Graph<V,E>	g
protected boolean	isDirected
protected V	startVertex
protected HierholzerEulerianCycle.VertexNode	verticesHead

Constructor Summary

Constructors

Constructor and Description
HierholzerEulerianCycle()

Method Summary

Modifier and Type	Method and Description
protected void	addEdge(HierholzerEulerianCycle.VertexNode sNode, HierholzerEulerianCycle.VertexNode tNode, E e) Add an edge to the index.
protected GraphWalk<V,E>	buildWalk() Build final walk
protected void	cleanup() Release any memory held.
protected Pair<HierholzerEulerianCycle.EdgeNode,HierholzerEulerianCycle.EdgeNode>	computePartialCycle() Computes a partial cycle assuming that all vertices have an even degree.
GraphPath<V,E>	getEulerianCycle(Graph<V,E> g) Compute an Eulerian cycle of a graph.
protected HierholzerEulerianCycle.VertexNode	getOppositeVertex(HierholzerEulerianCycle.VertexNode v, HierholzerEulerianCycle.EdgeNode e) Compute the opposite end-point of an end-point of an edge.
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.
boolean	isEulerian(Graph<V,E> graph) Test whether a graph is Eulerian.
protected void	moveToFront(HierholzerEulerianCycle.VertexNode vNode) Move a vertex as first in the vertex list.
protected void	unlink(HierholzerEulerianCycle.EdgeNode eNode) Unlink an edge from the adjacency lists of its end-points.
protected void	unlink(HierholzerEulerianCycle.VertexNode vNode) Unlink a vertex from the vertex list.
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.

Methods inherited from class java.lang.Object

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

Field Detail

g

protected Graph<V,E> g

isDirected

protected boolean isDirected

verticesHead

protected HierholzerEulerianCycle.VertexNode verticesHead

eulerianHead

protected HierholzerEulerianCycle.EdgeNode eulerianHead

startVertex

protected V startVertex

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

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

addEdge

protected void addEdge(HierholzerEulerianCycle.VertexNode sNode,
                       HierholzerEulerianCycle.VertexNode tNode,
                       E e)

Add an edge to the index.

Parameters:

sNode - source vertex

tNode - target vertex

e - original (wrapped) edge

unlink

protected void unlink(HierholzerEulerianCycle.VertexNode vNode)

Unlink a vertex from the vertex list.

Parameters:

vNode - vertex to unlink

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

getOppositeVertex

protected HierholzerEulerianCycle.VertexNode getOppositeVertex(HierholzerEulerianCycle.VertexNode v,
                                                               HierholzerEulerianCycle.EdgeNode e)

Compute the opposite end-point of an end-point of an edge.

Parameters:

v - vertex that is part of edge

e - edge used to find opposite vertex

Returns:

opposite vertex in edge