Yog.Multi.Eulerian (YogEx v0.97.0)

Copy Markdown View Source

Eulerian path and circuit detection for multigraphs.

An Eulerian path is a walk that traverses every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same node.

This module provides Hierholzer's algorithm adapted for multigraphs. In multigraphs, parallel edges between nodes are handled by using edge IDs rather than node pairs, ensuring unambiguous traversal.

Conditions for Eulerian Paths/Circuits

Undirected Graphs

  • Circuit: All nodes have even degree and the graph is connected
  • Path: Exactly 0 or 2 nodes have odd degree and the graph is connected

Directed Graphs

  • Circuit: Every node has equal in-degree and out-degree, and the graph is (weakly) connected
  • Path: At most one node with (out − in = 1), at most one with (in − out = 1), all others balanced; graph must be connected

Time Complexity

Examples

# Check if a graph has an Eulerian circuit
if Yog.Multi.Eulerian.has_eulerian_circuit?(graph) do
  {:ok, edge_ids} = Yog.Multi.Eulerian.find_eulerian_circuit(graph)
  # Traverse the circuit using edge_ids...
end

Summary

Functions

find_eulerian_circuit(graph)

Finds an Eulerian circuit using Hierholzer's algorithm adapted for multigraphs.

find_eulerian_path(graph)

Finds an Eulerian path using Hierholzer's algorithm adapted for multigraphs.

has_eulerian_circuit?(graph)

Returns true if the multigraph has an Eulerian circuit.

has_eulerian_path?(graph)

Returns true if the multigraph has an Eulerian path.

Functions

find_eulerian_circuit(graph)

@spec find_eulerian_circuit(Yog.Multi.Model.t()) ::
  {:ok, [Yog.Multi.Model.edge_id()]} | :error

Finds an Eulerian circuit using Hierholzer's algorithm adapted for multigraphs.

Returns the circuit as a list of EdgeIds, or :error if no circuit exists.

Important Note on Multigraphs

In multigraphs, parallel edges between the same pair of nodes cannot be distinguished by node IDs alone. This function returns a list of edge IDs, which unambiguously identify which specific edge to traverse at each step.

Time Complexity

O(E)

Examples

iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...>   |> Yog.Multi.Model.add_node(:c, "C")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :b, :c, 2), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :c, :a, 3), 0)
...> case Yog.Multi.Eulerian.find_eulerian_circuit(graph) do
...>   {:ok, edge_ids} -> length(edge_ids)
...>   :error -> 0
...> end
3

# No circuit exists
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> Yog.Multi.Eulerian.find_eulerian_circuit(graph)
:error

find_eulerian_path(graph)

@spec find_eulerian_path(Yog.Multi.Model.t()) ::
  {:ok, [Yog.Multi.Model.edge_id()]} | :error

Finds an Eulerian path using Hierholzer's algorithm adapted for multigraphs.

Returns the path as a list of EdgeIds, or :error if no path exists.

Important Note on Multigraphs

In multigraphs, parallel edges between the same pair of nodes cannot be distinguished by node IDs alone. This function returns a list of edge IDs, which unambiguously identify which specific edge to traverse at each step.

Time Complexity

O(E)

Examples

iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...>   |> Yog.Multi.Model.add_node(:c, "C")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :b, :c, 2), 0)
...> case Yog.Multi.Eulerian.find_eulerian_path(graph) do
...>   {:ok, edge_ids} -> length(edge_ids)
...>   :error -> 0
...> end
2

# A circuit is also a valid path
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...>   |> Yog.Multi.Model.add_node(:c, "C")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :b, :c, 2), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :c, :a, 3), 0)
...> case Yog.Multi.Eulerian.find_eulerian_path(graph) do
...>   {:ok, edge_ids} -> length(edge_ids)
...>   :error -> 0
...> end
3

# No path exists
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...>   |> Yog.Multi.Model.add_node(:c, "C")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :c, 2), 0)
...> Yog.Multi.Eulerian.find_eulerian_path(graph)
:error

has_eulerian_circuit?(graph)

@spec has_eulerian_circuit?(Yog.Multi.Model.t()) :: boolean()

Returns true if the multigraph has an Eulerian circuit.

An Eulerian circuit is a closed walk that traverses every edge exactly once.

Conditions

  • Undirected: all nodes have even degree and the graph is connected
  • Directed: every node has equal in-degree and out-degree and the graph is (weakly) connected

Time Complexity

O(V + E)

Examples

# A directed cycle has an Eulerian circuit
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...>   |> Yog.Multi.Model.add_node(:c, "C")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :b, :c, 2), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :c, :a, 3), 0)
...> Yog.Multi.Eulerian.has_eulerian_circuit?(graph)
true

# A path does not have an Eulerian circuit
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> Yog.Multi.Eulerian.has_eulerian_circuit?(graph)
false

# Empty graph has no circuit
iex> Yog.Multi.Eulerian.has_eulerian_circuit?(Yog.Multi.Model.directed())
false

has_eulerian_path?(graph)

@spec has_eulerian_path?(Yog.Multi.Model.t()) :: boolean()

Returns true if the multigraph has an Eulerian path.

An Eulerian path is an open walk that traverses every edge exactly once. Note that any graph with an Eulerian circuit also has an Eulerian path.

Conditions

  • Undirected: exactly 0 or 2 nodes have odd degree and the graph is connected
  • Directed: at most one node with (out − in = 1), at most one with (in − out = 1), all others balanced; graph must be connected

Time Complexity

O(V + E)

Examples

# A simple path has an Eulerian path
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> Yog.Multi.Eulerian.has_eulerian_path?(graph)
true

# A cycle also has an Eulerian path
iex> graph = Yog.Multi.Model.directed()
...>   |> Yog.Multi.Model.add_node(:a, "A")
...>   |> Yog.Multi.Model.add_node(:b, "B")
...>   |> Yog.Multi.Model.add_node(:c, "C")
...> graph = elem(Yog.Multi.Model.add_edge(graph, :a, :b, 1), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :b, :c, 2), 0)
...> graph = elem(Yog.Multi.Model.add_edge(graph, :c, :a, 3), 0)
...> Yog.Multi.Eulerian.has_eulerian_path?(graph)
true

# Empty graph has no path
iex> Yog.Multi.Eulerian.has_eulerian_path?(Yog.Multi.Model.directed())
false