Packages
fixpoint
0.11.2
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/kuhn2.ex
defmodule CPSolver.Algorithms.Kuhn2 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, fixed_matching \\ %{}, required_matching_size \\ nil) do
partial_matching = #fixed_matching
initial_matching(graph, left_partition, fixed_matching)
partition_size = MapSet.size(left_partition)
unmatched_limit =
((required_matching_size && required_matching_size - partition_size) || partition_size) -
map_size(partial_matching)
used = MapSet.new(Map.values(partial_matching))
Enum.reduce_while(
left_partition,
{partial_matching, MapSet.new(), unmatched_limit, MapSet.new()},
fn v, {matching_acc, visited_acc, unmatched_count, ga_da_acc} = acc ->
if MapSet.member?(used, v) do
{:cont, acc}
else
case augment(graph, v, matching_acc, visited_acc, ga_da_acc) do
## No augmenting path found for vertex v
{false, _matching, updated_visited, ga_da_acc} ->
## If the required size of matching can not be reached, we fail early.
case unmatched_count - 1 do
new_unmatched_count when new_unmatched_count < 0 ->
{:halt, false}
new_unmatched_count ->
{:cont, {matching_acc, updated_visited, new_unmatched_count, ga_da_acc}}
end
{true, increased_matching, ga_da} ->
{:cont, {increased_matching, MapSet.new(), unmatched_count, ga_da}}
end
end
end
)
|> then(fn
false ->
nil
{matching, _, _, ga_da} ->
{if required_matching_size do
map_size(matching) >= required_matching_size && matching
else
matching
end, ga_da}
end)
end
defp augment(graph, vertex, matching, visited_vertices, ga_da) do
if MapSet.member?(visited_vertices, vertex) do
## Skip already visited vertices
{false, matching, visited_vertices}
else
## Mark vertex as visited
updated_visited = MapSet.put(visited_vertices, vertex)
Enum.reduce_while(
Graph.neighbors(graph, vertex),
{false, matching, updated_visited, ga_da},
fn neighbor_vertex, {_path_found?, matching_acc, visited_acc, ga_da_acc} = acc ->
case Map.get(matching_acc, neighbor_vertex) do
nil ->
{:halt, {true, Map.put(matching_acc, neighbor_vertex, vertex), ga_da_acc}}
match when match == vertex ->
{:cont, acc}
match ->
case augment(
graph,
match,
matching_acc,
visited_acc,
ga_da_acc
) do
{false, _matching, _visited, _ga_da} = path_not_found ->
{:cont, path_not_found}
{true, new_matching, ga_da} ->
{:halt, {true, Map.put(new_matching, neighbor_vertex, vertex), ga_da}}
end
end
end
)
end
end
def initial_matching(graph, left_partition, fixed_matching \\ %{}) do
repaired_matching = # Remove matchings that are not edges
Enum.reduce(fixed_matching, fixed_matching, fn {right_vertex, left_vertex}, matching_acc ->
Enum.empty?(Graph.edges(graph, right_vertex, left_vertex)) && Map.delete(matching_acc, right_vertex) || matching_acc end)
Enum.reduce(left_partition, {repaired_matching, Map.values(repaired_matching) |> MapSet.new()}, fn ls_vertex, {_matching_acc, _used_left_acc} = acc->
Enum.reduce_while(
Graph.neighbors(graph, ls_vertex),
acc,
fn rs_vertex, {matching_acc2, used_left_acc2} = acc2 ->
Map.get(matching_acc2, rs_vertex) && {:cont, acc2} ||
(MapSet.member?(used_left_acc2, ls_vertex) && {:cont, acc2} ||
{:halt,
{Map.put(matching_acc2, rs_vertex, ls_vertex), MapSet.put(used_left_acc2, ls_vertex)}
})
end
)
end)
|> elem(0)
end
end