eulerian

Eulerian path and circuit algorithms for multigraphs.

This module provides algorithms for detecting and finding Eulerian paths and circuits in multigraphs. An Eulerian circuit is a closed walk that traverses every edge exactly once; an Eulerian path is an open walk with the same property.

Conditions for Existence

Graph Type	Circuit Exists	Path Exists
Undirected	All nodes have even degree	0 or 2 nodes have odd degree
Directed	All nodes balanced (in = out)	At most 1 start (out-in=1) and 1 end (in-out=1)

Available Functions

has_eulerian_circuit/1 - Check if an Eulerian circuit exists
has_eulerian_path/1 - Check if an Eulerian path exists
find_eulerian_circuit/1 - Find a circuit using Hierholzer’s algorithm
find_eulerian_path/1 - Find a path using Hierholzer’s algorithm

Time Complexity

Existence checks: O(V + E)
Finding circuits/paths: O(E)

References

Values

find_eulerian_circuit

</>

pub fn find_eulerian_circuit(
  graph: model.MultiGraph(n, e),
) -> option.Option(List(Int))

Finds an Eulerian circuit using Hierholzer’s algorithm adapted for multigraphs. The circuit is returned as a list of EdgeIds rather than node IDs, which avoids ambiguity when parallel edges exist.

Returns None if no Eulerian circuit exists.

Time Complexity: O(E)

find_eulerian_path

</>

pub fn find_eulerian_path(
  graph: model.MultiGraph(n, e),
) -> option.Option(List(Int))

Finds an Eulerian path using Hierholzer’s algorithm adapted for multigraphs. Returns the path as a list of EdgeIds. Returns None if no path exists.

Time Complexity: O(E)

has_eulerian_circuit

</>

pub fn has_eulerian_circuit(
  graph: model.MultiGraph(n, e),
) -> Bool

Returns True if the multigraph has an Eulerian circuit — 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)

has_eulerian_path

</>

pub fn has_eulerian_path(graph: model.MultiGraph(n, e)) -> Bool

Returns True if the multigraph has an Eulerian path — an open walk that traverses every edge exactly once.

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)