yog - v3.1.0

yog/properties/eulerian

Eulerian paths and circuits 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.

Values

find_eulerian_circuit

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

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

Returns the path as a list of node IDs forming a circuit.

Time Complexity: O(E)

find_eulerian_path

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

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

Returns the path as a list of node IDs.

Time Complexity: O(E)

has_eulerian_circuit

</> 
pub fn has_eulerian_circuit(graph: model.Graph(n, e)) -> Bool

Checks if the graph has an Eulerian circuit.

Conditions

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

Time Complexity: O(V + E)

has_eulerian_path

</> 
pub fn has_eulerian_path(graph: model.Graph(n, e)) -> Bool

Checks if the graph has 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.

Time Complexity: O(V + E)

✨ Search Document