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

Graph matching algorithms.

This module provides algorithms for finding matchings in graphs.
A matching is a set of edges without common vertices.

## Algorithms

| Problem | Algorithm | Function | Complexity |
|---------|-----------|----------|------------|
| Maximum bipartite matching | [Hopcroft-Karp](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm) | `hopcroft_karp/1` | O(E√V) |
| Weighted bipartite matching | [Hungarian (Kuhn-Munkres)](https://en.wikipedia.org/wiki/Hungarian_algorithm) | `hungarian/2` | O(V³) |
| Maximum general matching | [Edmonds' Blossom](https://en.wikipedia.org/wiki/Blossom_algorithm) | `blossom_maximum_matching/1` | O(V²E) |

## Key Concepts

- **Matching**: A set of edges with no shared vertices
- **Maximum Matching**: A matching with the largest possible number of edges
- **Perfect Matching**: Every vertex is matched (requires equal partitions)
- **Assignment Problem**: Optimal assignment of workers to jobs with costs/weights

## Examples

    iex> graph = Yog.from_edges(:undirected, [{:a1, :b1, 1}, {:a1, :b2, 1}, {:a2, :b2, 1}, {:a2, :b3, 1}])
    iex> matching = Yog.Matching.hopcroft_karp(graph)
    iex> map_size(matching)
    4
    iex> matching[:a1] in [:b1, :b2]
    true
    iex> matching[:a2] in [:b2, :b3]
    true
    iex> matching[:a1] != matching[:a2]

# `optimization`

```elixir
@type optimization() :: :min | :max
```

# `blossom_maximum_matching`

```elixir
@spec blossom_maximum_matching(Yog.Graph.t()) :: %{
  required(Yog.node_id()) => Yog.node_id()
}
```

Finds a maximum cardinality matching in a general (possibly non-bipartite) graph
using Edmonds' Blossom algorithm.

Unlike `hopcroft_karp/1`, this works on **any** undirected graph, including those
with odd cycles. The algorithm detects odd cycles (blossoms), contracts them into
super-vertices, and continues the search for augmenting paths.

Returns a bidirectional map where each matched pair appears twice
(`u => v` and `v => u`) for easy lookup in either direction.

## Examples

    # Triangle - odd cycle requires blossom contraction
    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> matching = Yog.Matching.blossom_maximum_matching(graph)
    iex> div(map_size(matching), 2)
    1

    # Square - even cycle, perfect matching exists
    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
    iex> matching = Yog.Matching.blossom_maximum_matching(graph)
    iex> div(map_size(matching), 2)
    2

    # Empty graph
    iex> matching = Yog.Matching.blossom_maximum_matching(Yog.undirected())
    iex> matching == %{}
    true

## Time Complexity

O(V²E) — practical for graphs up to ~1000 nodes.

## References

- [Wikipedia: Blossom algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm)
- Edmonds, J. (1965). "Paths, trees, and flowers"

# `hopcroft_karp`

```elixir
@spec hopcroft_karp(Yog.Graph.t()) :: %{required(Yog.node_id()) => Yog.node_id()}
```

Finds a maximum cardinality matching in a bipartite graph using the
Hopcroft-Karp algorithm.

The algorithm repeatedly finds a maximal set of shortest vertex-disjoint
augmenting paths via BFS layering, then augments the matching along each
path via DFS. This yields O(E√V) time complexity, significantly faster
than the naive O(VE) augmenting-path approach on dense graphs.

Returns a bidirectional map where each matched pair appears twice
(`u => v` and `v => u`) for easy lookup in either direction.

Raises `ArgumentError` if the input graph is not bipartite.

## Examples

    # Simple path graph
    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}])
    iex> matching = Yog.Matching.hopcroft_karp(graph)
    iex> map_size(matching)
    4

    # Star graph
    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {1, 3, 1}, {1, 4, 1}])
    iex> matching = Yog.Matching.hopcroft_karp(graph)
    iex> map_size(matching)
    2

    # Complete bipartite K_{2,2}
    iex> graph = Yog.from_edges(:undirected, [{:a1, :b1, 1}, {:a1, :b2, 1}, {:a2, :b1, 1}, {:a2, :b2, 1}])
    iex> matching = Yog.Matching.hopcroft_karp(graph)
    iex> map_size(matching)
    4

    # Empty graph
    iex> matching = Yog.Matching.hopcroft_karp(Yog.undirected())
    iex> matching == %{}
    true

## Time Complexity

O(E√V)

# `hungarian`

```elixir
@spec hungarian(Yog.Graph.t(), optimization()) ::
  {number(), %{required(Yog.node_id()) => Yog.node_id()}}
```

Finds a minimum or maximum weight perfect matching in a bipartite graph using
the Hungarian (Kuhn-Munkres) algorithm.

The graph must be bipartite. Rectangular partitions (|L| ≠ |R|) are padded with
dummy nodes at zero cost so the algorithm can proceed. Missing edges are not
supported: the graph must be complete between the two partitions.

Returns `{total_cost, matching}` where `matching` is a bidirectional map
(`u => v` and `v => u` for every matched pair). Dummy nodes are excluded from
the result.

## Examples

    iex> graph = Yog.from_edges(:undirected, [
    ...>   {:a, :x, 10}, {:a, :y, 19}, {:a, :z, 8},
    ...>   {:b, :x, 15}, {:b, :y, 17}, {:b, :z, 12},
    ...>   {:c, :x, 8},  {:c, :y, 18}, {:c, :z, 9}
    ...> ])
    iex> {cost, matching} = Yog.Matching.hungarian(graph, :min)
    iex> cost
    33
    iex> matching[:a]
    :z

---

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