yog - v5.1.1

yog/multi/eulerian

⚠️ Experimental Module

This module is experimental and provides minimal, working functionality. The implementation is functional but may not be fully optimized for performance.

Expected changes:

Use with caution in production environments.

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)

✨ Search Document