@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
• Edmonds, J. (1965). "Paths, trees, and flowers"

@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)

@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