defmodule CPSolver.Utils.MaximumMatching do
@moduledoc """
Algorithms for finding maximum matching on graphs.
"""
alias CPSolver.Common
import CPSolver.Utils
@spec build_flow_network([Common.variable_or_view()]) :: Graph.t()
def build_flow_network(variables) do
Enum.reduce(variables, {Graph.new(), 0}, fn var, {graph_acc, idx_acc} ->
values = domain_values(var)
{graph_acc
|> Graph.add_edge(:s, variable_node(idx_acc), weight: 1)
|> then(fn g ->
Enum.reduce(values, g, fn val, g_acc ->
g_acc
|> Graph.add_edge(variable_node(idx_acc), value_node(idx_acc, val), weight: 1)
|> Graph.add_edge(value_node(idx_acc, val), :t, weight: 1)
end)
end), idx_acc + 1}
end)
|> elem(0)
end
defp variable_node(idx) do
{:variable, idx}
end
defp value_node(_var_idx, value) do
{:value, value}
end
end