defmodule CPSolver.Algorithms.Kuhn do
@moduledoc """
Kuhn's algorithm to find maximal matching in bipartite graph.
https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html
"""

@doc """
Given the bipartite graph, a list of it's left-part vertices,
and (optional) initial matching %{right_side_vertex => left_side_vertex},
find maximal matching
"""
@spec kuhn(Graph.t(), [any()], map()) :: map()
def kuhn(%Graph{} = graph, left_part_vertices, partial_matching \\ %{}) do
  Enum.reduce(left_part_vertices, partial_matching,
    fn v, match_acc ->
      match = dfs(graph, v, match_acc)
      match && Map.put(match_acc, v) || match_acc
  end)
end

defp dfs(graph, vertex, partial_matching) do

end

end