Packages
fixpoint
0.11.2
0.22.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
test/algos/kuhn_test.exs
defmodule CPSolverTest.Algorithms.Kuhn do
alias CPSolver.Algorithms.Kuhn
use ExUnit.Case, async: false
@three_vertices_instance [[1, 2], [1, 2], [1, 2, 3, 4]]
@six_vertices_instance [
[1, 4, 5],
[9, 10],
[1, 4, 5, 8, 9],
[1, 4, 5],
[1, 4, 5, 8, 9],
[1, 4, 5]
]
@maximum_2_instance [[1, 2, 3], [1, 2, 3]]
describe "Kuhn maximal matching" do
test "3 vertices in left-side partition" do
right_side_neighbors = @three_vertices_instance
{bp_graph, left_partition} = build_bp_graph(right_side_neighbors)
matching = Kuhn.run(bp_graph, left_partition)
assert_matching(matching, 3)
bp_graph2 = Graph.delete_edge(bp_graph, {:L, 3}, {:R, 3})
matching2 = Kuhn.run(bp_graph2, left_partition)
assert_matching(matching2, 3)
bp_graph3 = Graph.delete_edge(bp_graph2, {:L, 3}, {:R, 4})
## 3 nodes in the left partition, 2 nodes in the right partition
matching3 = Kuhn.run(bp_graph3, left_partition)
assert_matching(matching3, 2)
end
test "6 vertices in left-side partition" do
right_side_neighbors = @six_vertices_instance
{bp_graph, left_partition} = build_bp_graph(right_side_neighbors)
matching = Kuhn.run(bp_graph, left_partition)
assert_matching(matching, 6)
bp_graph2 = Graph.delete_edge(bp_graph, {:L, 6}, {:R, 5})
matching2 = Kuhn.run(bp_graph2, left_partition)
assert_matching(matching2, 6)
bp_graph3 =
bp_graph2
|> Graph.delete_edge({:L, 1}, {:R, 5})
|> Graph.delete_edge({:L, 4}, {:R, 5})
matching3 = Kuhn.run(bp_graph3, left_partition)
assert_matching(matching3, 5)
end
test "initial_matching (3 vertices)" do
right_side_neighbors = @three_vertices_instance
{bp_graph, left_partition} = build_bp_graph(right_side_neighbors)
initial_matching = Kuhn.initial_matching(bp_graph, left_partition)
assert_matching(Kuhn.run(bp_graph, left_partition, initial_matching), 3)
end
test "initial_matching (6 vertices)" do
right_side_neighbors = @six_vertices_instance
{bp_graph, left_partition} = build_bp_graph(right_side_neighbors)
initial_matching = Kuhn.initial_matching(bp_graph, left_partition)
initial_matching = Kuhn.initial_matching(bp_graph, left_partition, initial_matching)
assert_matching(Kuhn.run(bp_graph, left_partition, initial_matching), 6)
end
test "no matching of required size" do
right_side_neighbors = @maximum_2_instance
{bp_graph, left_partition} = build_bp_graph(right_side_neighbors)
## Can't have matching size of 3
refute Kuhn.run(bp_graph, left_partition, %{}, 3)
end
test "fixed matchings that are not edges will be ignored" do
right_side_neighbors = @maximum_2_instance
{bp_graph, left_partition} = build_bp_graph(right_side_neighbors)
## There is no value 0 for any of the left-side vertices
non_value_edge = %{{:R, 0} => {:L, 1}}
refute {:R, 0} in (Kuhn.run(bp_graph, left_partition, non_value_edge) |> Map.keys())
non_variable_edge = %{{:R, 1} => {:L, 0}}
refute {:L, 0} in (Kuhn.run(bp_graph, left_partition, non_variable_edge) |> Map.values())
end
end
defp build_bp_graph(right_side_neighbors) do
left_partition = Enum.map(1..length(right_side_neighbors), fn idx -> {:L, idx} end)
graph_input = Enum.zip(left_partition, right_side_neighbors)
bp_graph =
Enum.reduce(graph_input, Graph.new(), fn {ls_vertex, rs_neighbors}, g_acc ->
edges = Enum.map(rs_neighbors, fn rsn -> {ls_vertex, {:R, rsn}} end)
Graph.add_edges(g_acc, edges)
end)
{bp_graph, MapSet.new(left_partition)}
end
defp assert_matching(matching, size) do
assert size == map_size(matching)
assert size == Map.values(matching) |> Enum.uniq() |> length()
end
end