Packages
fixpoint
0.9.5
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/algos/kuhn.ex
defmodule CPSolver.Algorithms.Kuhn do
@moduledoc """
Kuhn's algorithm to find maximum matching in bipartite graph.
https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html
"""
@doc """
Given the bipartite graph, a list of vertices int the left partition,
and (optional) partial matching %{right_side_vertex => left_side_vertex},
find maximum matching
"""
@spec run(Graph.t(), [any()], map()) :: map()
def run(%Graph{} = graph, left_partition, partial_matching \\ %{}) do
used = MapSet.new(Map.values(partial_matching))
Enum.reduce(
left_partition,
{partial_matching, MapSet.new()},
fn v, {matching_acc, visited_acc} = acc ->
if MapSet.member?(used, v) do
acc
else
case augment(graph, v, matching_acc, visited_acc) do
## No augmented path found
{false, _matching, updated_visited} -> {matching_acc, updated_visited}
{true, increased_matching} -> {increased_matching, MapSet.new()}
end
end
end
)
|> elem(0)
end
defp augment(graph, ls_vertex, matching, visited_vertices) do
if MapSet.member?(visited_vertices, ls_vertex) do
{false, matching, visited_vertices}
else
updated_visited = MapSet.put(visited_vertices, ls_vertex)
Enum.reduce_while(
Graph.neighbors(graph, ls_vertex),
{false, matching, updated_visited},
fn rs_vertex, {_found?, matching_acc, visited_acc} ->
case Map.get(matching_acc, rs_vertex) do
nil ->
{:halt, {true, Map.put(matching_acc, rs_vertex, ls_vertex)}}
match ->
case augment(
graph,
match,
matching_acc,
visited_acc
) do
{false, _matching, _visited} = path_not_found ->
{:cont, path_not_found}
{true, new_matching} ->
{:halt, {true, Map.put(new_matching, rs_vertex, ls_vertex)}}
end
end
end
)
end
end
def initial_matching(graph, left_partition) do
Enum.reduce(left_partition, Map.new(), fn ls_vertex, partial_matching ->
Enum.reduce_while(
Graph.neighbors(graph, ls_vertex),
partial_matching,
fn rs_vertex, matching_acc ->
(Map.get(matching_acc, rs_vertex) && {:cont, matching_acc}) ||
{:halt, Map.put(matching_acc, rs_vertex, ls_vertex)}
end
)
end)
end
end