@spec blossom_maximum_matching(
  Zog.SoA.t() | Zog.ResourceGraph.t(),
  keyword()
) :: %{required(Zog.SoA.label()) => Zog.SoA.label()}

Computes maximum cardinality matching on general (non-bipartite) graphs using Edmonds' Blossom algorithm.

Delegates to Zog.Connectivity.blossom_maximum_matching/1 for Zog.SoA builders or Zog.ResourceGraph.blossom_maximum_matching/2 for Zog.ResourceGraph.

Returns a map %{u => v, v => u} representing matched vertex pairs.

@spec hungarian(
  Zog.SoA.t() | Zog.ResourceGraph.t(),
  keyword()
) :: {float(), %{required(Zog.SoA.label()) => Zog.SoA.label()}}

Calculates weighted bipartite matching using the O(V³) Hungarian (Kuhn-Munkres) algorithm.

Delegates to Zog.Connectivity.hungarian/2 for Zog.SoA builders or Zog.ResourceGraph.hungarian/2 for Zog.ResourceGraph.

Examples

iex> builder = Zog.undirected()
...> |> Zog.add_edge("a", "x", 10.0)
...> |> Zog.add_edge("a", "y", 19.0)
...> |> Zog.add_edge("b", "x", 15.0)
...> |> Zog.add_edge("b", "y", 14.0)
iex> {cost, matching} = Zog.Matching.hungarian(builder, optimization: :min)
iex> cost
24.0
iex> matching["a"]
"x"

@spec maximum_bipartite_matching(
  Zog.SoA.t() | Zog.ResourceGraph.t(),
  keyword()
) :: {:ok, [{Zog.SoA.label(), Zog.SoA.label()}]} | {:error, :not_bipartite}

Computes maximum cardinality bipartite matching using the Hopcroft-Karp algorithm.