Find an Eulerian Path with the Hierholzer Algorithm
An Eulerian path of a graph is a path that passes once on every edge of the graph.
The Hierholzer algorithm allows to find this path.
The algorithm proceeds as follows:
- Choose any vertex $v_0$ of the graph $G = (V, E)$. Starting from $v_0$, build a path $c$ that passes only once per edge until it reaches $v_0$ again.
- If $c$ is an Eulerian cycle, we have found the Eulerian path, else
- Ignore all edges from $c$.
- For the first vertex $u$ from $c$ whose degree is not null, build an other cycle $c’$ that passes only once per edges, and does not pass in the previously visited edges.
- Insert $c’$ in $c$ by replacing the starting node $u$.
- Repeat the second step until we have an Eulerian path.
Pseudocode
\begin{algorithm} \caption{Hierholzer algorithm for Eulerian path finding} \begin{algorithmic} \Function{EulerianPath}{$G: (V, E)$} \State $c \gets$ an empty Doubly Linked List \State $E' \gets E$ \State $v_0$ becomes the first vertex from $V$ \State $u \gets v_0$ \State \Comment{Find the first cycle} \While{$\exists (u, v) \in E'$} \State $c$.insert($u$) \State $u \gets v$ \State $E' \gets E' \setminus \{(u, v)\}$ \If {$u = v_0$} \Break \EndIf \EndWhile \State \Comment{Add the other cycles} \While {$c$.length $< |E|$} \State \Comment{Find the next vertex with non null degree} \State $v_0 \gets c$.value \While {$\nexists (v_0, v) \in E'$} \State $c \gets c$.next \State $v_0 \gets c$.value \State $u \gets v_0$ \EndWhile \State \Comment{Insert the next cycle in $c$} \State $c$.delete() \Comment{Ensure $v_0$ is not present twice there} \While {$\exists (u, v) \in E'$} \State $c$.insert($u$) \State $u \gets v$ \State $E' \gets E' \setminus \{(u, v)\}$ \If {$u = v_0$} \Break \EndIf \EndWhile \EndWhile \EndFunction \end{algorithmic} \end{algorithm}
Rust implantation
use std::collections::{HashMap, LinkedList};
use std::io::Error;
/// Eulerian path
///
/// Warning: this assumes the graph is Eulerian
fn eulerian_path(graph: HashMap<usize, Vec<usize>>) -> Option<LinkedList<usize>>
{
let mut n_edges: usize = 0;
for adj_list in graph.values() {
n_edges += adj_list.len();
}
let mut graph = graph.clone();
let mut cycle: LinkedList<usize> = LinkedList::new();
let v_0: usize = *graph.keys().next().unwrap();
let mut visited_edges: usize = 0;
let mut u: usize = v_0;
loop {
cycle.push_back(u);
let adj_list = graph.get_mut(&u).unwrap();
visited_edges += 1;
if adj_list.len() > 0 {
let v = adj_list.pop().unwrap();
u = v;
} else {
return None;
}
if u == v_0 {
break;
}
}
while visited_edges < n_edges {
// Find the next vertex with non null degree
let mut v_0 = cycle.front().unwrap().clone();
while graph.get(&v_0).unwrap().len() == 0 {
v_0 = cycle.front().unwrap().clone();
// Move to the next vertex without removing it from the cycle, with rotation
let v = cycle.pop_front().unwrap();
cycle.push_back(v);
}
// Insert the next cycle in c
cycle.pop_back();
let mut u = v_0;
loop {
cycle.push_back(u);
let adj_list = graph.get_mut(&u).unwrap();
visited_edges += 1;
if adj_list.len() > 0 {
let v = adj_list.pop().unwrap();
u = v;
} else {
return None;
}
if u == v_0 {
break;
}
}
}
Some(cycle)
}
References
- Algorithmus von Hierholzer (de), Wikipedia, https://de.wikipedia.org/wiki/Algorithmus_von_Hierholzer.
- Eulerkreisproblem (de), Wikipedia, https://de.wikipedia.org/wiki/Eulerkreisproblem