Package org.jgrapht.alg.cycle
Class HierholzerEulerianCycle<V,E>
- java.lang.Object
-
- org.jgrapht.alg.cycle.HierholzerEulerianCycle<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
HierholzerEulerianCycle.EdgeNode
(package private) class
HierholzerEulerianCycle.VertexNode
-
Field Summary
Fields Modifier and Type Field Description private HierholzerEulerianCycle.EdgeNode
eulerianHead
private Graph<V,E>
g
private boolean
isDirected
private HierholzerEulerianCycle.VertexNode
verticesHead
-
Constructor Summary
Constructors Constructor Description HierholzerEulerianCycle()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addEdge(HierholzerEulerianCycle.VertexNode sNode, HierholzerEulerianCycle.VertexNode tNode, E e)
private GraphWalk<V,E>
buildWalk()
Build final walkprivate void
cleanup()
Release any memory held.private 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.private HierholzerEulerianCycle.VertexNode
getOppositeVertex(HierholzerEulerianCycle.VertexNode v, HierholzerEulerianCycle.EdgeNode e)
private 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.private void
moveToFront(HierholzerEulerianCycle.VertexNode vNode)
private void
unlink(HierholzerEulerianCycle.EdgeNode eNode)
private void
unlink(HierholzerEulerianCycle.VertexNode vNode)
private 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.
-
-
-
Field Detail
-
isDirected
private boolean isDirected
-
verticesHead
private HierholzerEulerianCycle.VertexNode verticesHead
-
eulerianHead
private HierholzerEulerianCycle.EdgeNode eulerianHead
-
-
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 interfaceEulerianCycleAlgorithm<V,E>
- Parameters:
g
- the input graph- Returns:
- an Eulerian cycle
- Throws:
java.lang.IllegalArgumentException
- in case the graph is not Eulerian
-
initialize
private 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
private void cleanup()
Release any memory held.
-
computePartialCycle
private 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
private 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 cyclepartialCycleStartVertex
- the source vertex of the first edge in the partial cycle
-
addEdge
private void addEdge(HierholzerEulerianCycle.VertexNode sNode, HierholzerEulerianCycle.VertexNode tNode, E e)
-
unlink
private void unlink(HierholzerEulerianCycle.VertexNode vNode)
-
moveToFront
private void moveToFront(HierholzerEulerianCycle.VertexNode vNode)
-
unlink
private void unlink(HierholzerEulerianCycle.EdgeNode eNode)
-
getOppositeVertex
private HierholzerEulerianCycle.VertexNode getOppositeVertex(HierholzerEulerianCycle.VertexNode v, HierholzerEulerianCycle.EdgeNode e)
-
-