Yog.Property.Eulerian (YogEx v0.97.0)

Copy Markdown View Source

Eulerian path and circuit algorithms using Hierholzer's algorithm.

An Eulerian path visits every edge exactly once. An Eulerian circuit visits every edge exactly once and returns to the start. These problems originated from the famous Seven Bridges of Königsberg solved by Leonhard Euler in 1736, founding graph theory.

Algorithms

ProblemAlgorithmFunctionComplexity
Eulerian circuit checkDegree countinghas_eulerian_circuit?/1O(V + E)
Eulerian path checkDegree countinghas_eulerian_path?/1O(V + E)
Find circuitHierholzer'seulerian_circuit/1O(E)
Find pathHierholzer'seulerian_path/1O(E)

Key Concepts

  • Eulerian Circuit: Closed walk using every edge exactly once
  • Eulerian Path: Open walk using every edge exactly once
  • Eulerian Graph: Graph with an Eulerian circuit
  • Semi-Eulerian Graph: Graph with an Eulerian path but no circuit

Necessary and Sufficient Conditions

Undirected Graphs:

  • Circuit: All vertices have even degree, connected (ignoring isolates)
  • Path: Exactly 0 or 2 vertices have odd degree, connected

Directed Graphs:

  • Circuit: In-degree = Out-degree for all vertices, weakly connected
  • Path: At most one vertex has (out - in) = 1 (start), at most one has (in - out) = 1 (end), all others balanced

Hierholzer's Algorithm

  1. Start from any vertex (or odd-degree vertex for path)
  2. Follow unused edges until returning to start (forming a cycle)
  3. If unused edges remain, find vertex on current path with unused edges
  4. Form another cycle from that vertex and splice into main path
  5. Repeat until all edges used

Relationship to Other Problems

  • Chinese Postman: Find shortest closed walk using every edge at least once (adds duplicate edges to make graph Eulerian)
  • Route Inspection: Variant allowing non-closed walks
  • Hamiltonian Path: Visits every vertex once (much harder, NP-complete)

Use Cases

  • Route optimization: Minimizing distance in postal delivery or snow plowing

Eulerian Visualization

An Eulerian Circuit exists if every vertex has an even degree. An Eulerian Path exists if exactly zero or two vertices have an odd degree.

graph G { rankdir=LR; bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_circuit { label="Eulerian Circuit (All Even)"; color="#10b981"; style=rounded; A -- B; B -- C; C -- A; C -- D; D -- E; E -- C; } subgraph cluster_path { label="Eulerian Path (2 Odd)"; color="#f59e0b"; style=rounded; 1 -- 2; 2 -- 3; 3 -- 4; 4 -- 1; 1 -- 3; } }
iex> alias Yog.Property.Eulerian
iex> circuit = Yog.from_edges(:undirected, [{"A", "B", 1}, {"B", "C", 1}, {"C", "A", 1}, {"C", "D", 1}, {"D", "E", 1}, {"E", "C", 1}])
iex> Eulerian.has_eulerian_circuit?(circuit)
true
iex> path = Yog.from_edges(:undirected, [{"1", "2", 1}, {"2", "3", 1}, {"3", "4", 1}, {"4", "1", 1}, {"1", "3", 1}])
iex> Eulerian.has_eulerian_path?(path)
true
iex> Eulerian.has_eulerian_circuit?(path)
false

History

In 1736, Leonhard Euler proved that the Seven Bridges of Königsberg problem had no solution, establishing the conditions for Eulerian paths and founding graph theory as a mathematical discipline.

Examples

# Simple Eulerian circuit (square)
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 4, to: 1, with: 1)
iex> Yog.Property.Eulerian.has_eulerian_circuit?(graph)
true

References

Summary

Functions

eulerian_circuit(graph)

Finds an Eulerian circuit in the graph using Hierholzer's algorithm.

eulerian_path(graph)

Finds an Eulerian path in the graph using Hierholzer's algorithm.

has_eulerian_circuit?(graph)

Checks if the graph contains an Eulerian circuit.

has_eulerian_path?(graph)

Checks if the graph contains an Eulerian path.

Functions

eulerian_circuit(graph)

@spec eulerian_circuit(Yog.graph()) ::
  {:ok, [Yog.node_id()]} | {:error, :no_eulerian_circuit}

Finds an Eulerian circuit in the graph using Hierholzer's algorithm.

Returns {:ok, circuit} where circuit is a list of node IDs forming a circuit, or {:error, :no_eulerian_circuit} if no circuit exists.

Examples

# Find circuit in square
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 4, to: 1, with: 1)
iex> {:ok, circuit} = Yog.Property.Eulerian.eulerian_circuit(graph)
iex> length(circuit)
5  # Includes return to start

# No circuit in path graph
iex> path = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Eulerian.eulerian_circuit(path)
{:error, :no_eulerian_circuit}

Time Complexity

O(E)

eulerian_path(graph)

@spec eulerian_path(Yog.graph()) ::
  {:ok, [Yog.node_id()]} | {:error, :no_eulerian_path}

Finds an Eulerian path in the graph using Hierholzer's algorithm.

Returns {:ok, path} where path is a list of node IDs, or {:error, :no_eulerian_path} if no path exists.

Examples

# Find path in path graph
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> {:ok, path} = Yog.Property.Eulerian.eulerian_path(graph)
iex> length(path)
3

# Path in square (starts and ends at same node since it has circuit)
iex> square = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 4, to: 1, with: 1)
iex> {:ok, path} = Yog.Property.Eulerian.eulerian_path(square)
iex> length(path)
5

Time Complexity

O(E)

has_eulerian_circuit?(graph)

@spec has_eulerian_circuit?(Yog.graph()) :: boolean()

Checks if the graph contains an Eulerian circuit.

Conditions

  • Undirected: All vertices even degree + connected.
  • Directed: All vertices balanced (in == out) + connected.

Examples

# Square has Eulerian circuit (all degrees = 2)
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 4, to: 1, with: 1)
iex> Yog.Property.Eulerian.has_eulerian_circuit?(graph)
true

# Path does not have circuit (ends have odd degree)
iex> path = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Eulerian.has_eulerian_circuit?(path)
false

# Empty graph has no circuit
iex> Yog.Property.Eulerian.has_eulerian_circuit?(Yog.undirected())
false

Time Complexity

O(V + E)

has_eulerian_path?(graph)

@spec has_eulerian_path?(Yog.graph()) :: boolean()

Checks if the graph contains an Eulerian path.

Conditions

  • Undirected: 0 or 2 odd-degree vertices + connected.
  • Directed: At most one (out - in = 1), at most one (in - out = 1), others balanced.

Examples

# Path graph has Eulerian path (2 odd-degree vertices)
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Eulerian.has_eulerian_path?(graph)
true

# Square has path (actually has circuit)
iex> square = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 4, to: 1, with: 1)
iex> Yog.Property.Eulerian.has_eulerian_path?(square)
true

# Empty graph has no path
iex> Yog.Property.Eulerian.has_eulerian_path?(Yog.undirected())
false

Time Complexity

O(V + E)