810 Fundamental

810-eulerian-path — Eulerian Path

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "810-eulerian-path — Eulerian Path" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. An Eulerian path visits every edge exactly once. Key difference from OCaml: 1. **Edge consumption**: Rust removes edges from `adj[v]` using `pop`; OCaml uses list tails — both avoid revisiting edges.

Tutorial

The Problem

An Eulerian path visits every edge exactly once. Euler proved in 1736 (the Königsberg bridge problem — the first graph theory result) that an Eulerian path exists if and only if exactly 0 or 2 vertices have odd degree (directed: out-degree − in-degree = ±1 for endpoints, 0 for all others). Eulerian circuits (closed paths) require all vertices to have equal in/out-degree. Applications include printed circuit board routing, DNA sequence assembly (de Bruijn graphs), and postman route optimization.

🎯 Learning Outcomes

• Check the Eulerian path existence condition: exactly 0 or 2 vertices with odd degree in undirected, specific in/out conditions in directed

• Find the start vertex: the vertex with out-degree > in-degree (or any vertex for Eulerian circuit)

• Implement Hierholzer's algorithm: DFS with backtracking to build the path

• Understand why Hierholzer's works: extend the path until stuck, then splice in detours

• Apply to DNA assembly: reads as edges in a de Bruijn graph → Eulerian path = assembled sequence

Code Example

#![allow(clippy::all)]
//! # Eulerian Path
pub fn eulerian_path(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
    let mut deg = vec![[0, 0]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        deg[u][0] += 1;
        deg[v][1] += 1;
    }
    let (mut start, mut end) = (None, None);
    for v in 0..n {
        let diff = deg[v][0] as i32 - deg[v][1] as i32;
        match diff {
            1 => {
                if start.is_some() {
                    return None;
                } else {
                    start = Some(v);
                }
            }
            -1 => {
                if end.is_some() {
                    return None;
                } else {
                    end = Some(v);
                }
            }
            0 => {}
            _ => return None,
        }
    }
    let start = start.unwrap_or(0);
    let mut path = vec![];
    let mut stack = vec![start];
    while let Some(&v) = stack.last() {
        if adj[v].is_empty() {
            path.push(v);
            stack.pop();
        } else {
            let u = adj[v].pop().unwrap();
            stack.push(u);
        }
    }
    path.reverse();
    if path.len() != edges.len() + 1 {
        None
    } else {
        Some(path)
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_euler() {
        let p = eulerian_path(4, &[(0, 1), (1, 2), (2, 0), (0, 3), (3, 0)]);
        assert!(p.is_some());
    }
}

(* Eulerian Path/Circuit — Hierholzer's algorithm O(V+E) *)
(* Undirected graph represented as adjacency list with edge indices *)

let eulerian_path adj n =
  (* Check degrees *)
  let degree = Array.init n (fun i -> List.length adj.(i)) in
  let odd_verts = Array.to_list (Array.init n (fun i -> (i, degree.(i))))
                  |> List.filter (fun (_, d) -> d mod 2 <> 0)
                  |> List.map fst
  in
  let start = match odd_verts with
    | []    -> 0           (* circuit: start anywhere *)
    | [s;_] -> s           (* path: start at odd vertex *)
    | _     -> failwith "No Eulerian path exists (not 0 or 2 odd vertices)"
  in
  (* Mutable adjacency: array of (neighbor, used) list refs *)
  let edges = Array.init n (fun i ->
    ref (List.map (fun v -> (v, ref false)) adj.(i))
  ) in
  let stack  = ref [start] in
  let circuit = ref [] in
  while !stack <> [] do
    let v = List.hd !stack in
    (* Find first unused edge from v *)
    let rec find_edge = function
      | [] -> None
      | (u, used) :: rest ->
        if not !used then Some (u, used, rest)
        else find_edge rest
    in
    match find_edge !(edges.(v)) with
    | None ->
      circuit := v :: !circuit;
      stack   := List.tl !stack
    | Some (u, used, _) ->
      used   := true;
      (* Also mark reverse edge *)
      edges.(u) := List.map (fun (w, f) ->
        if w = v && not !f then (used := true; (w, f))  (* mark one instance *)
        else (w, f)
      ) !(edges.(u));
      stack := u :: !stack
  done;
  !circuit

let () =
  (* Simple circuit: 0-1-2-0 *)
  let n   = 3 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  add 0 1; add 1 2; add 2 0;
  let circuit = eulerian_path adj n in
  Printf.printf "Triangle circuit: [%s]\n"
    (String.concat " -> " (List.map string_of_int circuit))

Key Differences

Edge consumption: Rust removes edges from adj[v] using pop; OCaml uses list tails — both avoid revisiting edges.

Degree check: Directed Eulerian path requires exactly one vertex with out-degree = in-degree + 1 (start) and one with in-degree = out-degree + 1 (end); both languages check this identically.

DNA assembly: de Bruijn graphs for genome assembly use k-mers as vertices and (k-1)-mer overlaps as edges; the assembled genome is the Eulerian path.

Hierholzer vs Fleury: Fleury's algorithm (bridge-avoiding) is O(E²); Hierholzer's is O(E) — always use Hierholzer's.

OCaml Approach

OCaml implements with Array.make n [] for adjacency and Array.make n 0 for degree tracking. Hierholzer's stack uses a list ref. OCaml's List.tl advances the adjacency list. The de Bruijn graph construction for DNA assembly is a natural OCaml application given its string processing strengths. Ocamlgraph.Euler provides a clean implementation.

Full Source

#![allow(clippy::all)]
//! # Eulerian Path
pub fn eulerian_path(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
    let mut deg = vec![[0, 0]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        deg[u][0] += 1;
        deg[v][1] += 1;
    }
    let (mut start, mut end) = (None, None);
    for v in 0..n {
        let diff = deg[v][0] as i32 - deg[v][1] as i32;
        match diff {
            1 => {
                if start.is_some() {
                    return None;
                } else {
                    start = Some(v);
                }
            }
            -1 => {
                if end.is_some() {
                    return None;
                } else {
                    end = Some(v);
                }
            }
            0 => {}
            _ => return None,
        }
    }
    let start = start.unwrap_or(0);
    let mut path = vec![];
    let mut stack = vec![start];
    while let Some(&v) = stack.last() {
        if adj[v].is_empty() {
            path.push(v);
            stack.pop();
        } else {
            let u = adj[v].pop().unwrap();
            stack.push(u);
        }
    }
    path.reverse();
    if path.len() != edges.len() + 1 {
        None
    } else {
        Some(path)
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_euler() {
        let p = eulerian_path(4, &[(0, 1), (1, 2), (2, 0), (0, 3), (3, 0)]);
        assert!(p.is_some());
    }
}

(* Eulerian Path/Circuit — Hierholzer's algorithm O(V+E) *)
(* Undirected graph represented as adjacency list with edge indices *)

let eulerian_path adj n =
  (* Check degrees *)
  let degree = Array.init n (fun i -> List.length adj.(i)) in
  let odd_verts = Array.to_list (Array.init n (fun i -> (i, degree.(i))))
                  |> List.filter (fun (_, d) -> d mod 2 <> 0)
                  |> List.map fst
  in
  let start = match odd_verts with
    | []    -> 0           (* circuit: start anywhere *)
    | [s;_] -> s           (* path: start at odd vertex *)
    | _     -> failwith "No Eulerian path exists (not 0 or 2 odd vertices)"
  in
  (* Mutable adjacency: array of (neighbor, used) list refs *)
  let edges = Array.init n (fun i ->
    ref (List.map (fun v -> (v, ref false)) adj.(i))
  ) in
  let stack  = ref [start] in
  let circuit = ref [] in
  while !stack <> [] do
    let v = List.hd !stack in
    (* Find first unused edge from v *)
    let rec find_edge = function
      | [] -> None
      | (u, used) :: rest ->
        if not !used then Some (u, used, rest)
        else find_edge rest
    in
    match find_edge !(edges.(v)) with
    | None ->
      circuit := v :: !circuit;
      stack   := List.tl !stack
    | Some (u, used, _) ->
      used   := true;
      (* Also mark reverse edge *)
      edges.(u) := List.map (fun (w, f) ->
        if w = v && not !f then (used := true; (w, f))  (* mark one instance *)
        else (w, f)
      ) !(edges.(u));
      stack := u :: !stack
  done;
  !circuit

let () =
  (* Simple circuit: 0-1-2-0 *)
  let n   = 3 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  add 0 1; add 1 2; add 2 0;
  let circuit = eulerian_path adj n in
  Printf.printf "Triangle circuit: [%s]\n"
    (String.concat " -> " (List.map string_of_int circuit))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_euler() {
        let p = eulerian_path(4, &[(0, 1), (1, 2), (2, 0), (0, 3), (3, 0)]);
        assert!(p.is_some());
    }
}

Deep Comparison

OCaml vs Rust: Eulerian Path

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement eulerian_circuit_undirected(n, edges) for undirected graphs: check that all vertices have even degree and find the circuit.

Construct the de Bruijn graph for a set of k-mer reads and find the Eulerian path to assemble the DNA sequence.

Apply Eulerian path to the "Chinese Postman Problem": find the minimum weight closed walk that covers all edges, adding minimum weight duplicate edges to fix odd-degree vertices.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust