# `Yog.Multi.Eulerian`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/multi/eulerian.ex#L1)

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

- Detection functions (`has_eulerian_circuit?/1`, `has_eulerian_path?/1`): O(V + E)
- Finding functions (`find_eulerian_circuit/1`, `find_eulerian_path/1`): O(E)

## 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

# `find_eulerian_circuit`

```elixir
@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 `EdgeId`s, 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`

```elixir
@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 `EdgeId`s, 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?`

```elixir
@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?`

```elixir
@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

---

*Consult [api-reference.md](api-reference.md) for complete listing*