# `Yog.Pathfinding.ChinesePostman`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.5/lib/yog/pathfinding/chinese_postman.ex#L1)

The [Chinese Postman Problem](https://en.wikipedia.org/wiki/Route_inspection_problem)
(also known as the Route Inspection Problem).

Finds the shortest closed walk that traverses every edge of an undirected graph
at least once. For Eulerian graphs, this is simply the Eulerian circuit. For
graphs with odd-degree vertices, the algorithm:

1. Finds all odd-degree vertices
2. Computes shortest paths between all pairs of odd vertices
3. Finds a minimum-weight perfect matching on the odd vertices
4. Duplicates the matched shortest-path edges to make the graph Eulerian
5. Extracts an Eulerian circuit from the augmented multigraph

## Complexity

- Finding odd vertices: O(V)
- All-pairs shortest paths: O(k × (E + V log V)) where k = number of odd vertices
- Minimum-weight perfect matching: O(k² × 2^k) via DP (efficient for small k)
- Eulerian circuit: O(E)

## Examples

    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> {:ok, _path, weight} = Yog.Pathfinding.ChinesePostman.chinese_postman(graph)
    iex> weight
    4

# `chinese_postman`

```elixir
@spec chinese_postman(Yog.Graph.t()) ::
  {:ok, [Yog.node_id()], number()} | {:error, :no_solution}
```

Solves the Chinese Postman Problem for an undirected graph.

Returns `{:ok, path_nodes, total_weight}` where `path_nodes` is a closed walk
covering every edge at least once, or `{:error, :no_solution}` if the graph is
empty, directed, or disconnected.

---

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