Packages
fixpoint
0.9.7
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]
]
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)
assert_matching(Kuhn.run(bp_graph, left_partition, initial_matching), 6)
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, left_partition}
end
defp assert_matching(matching, size) do
assert size == map_size(matching)
assert size == Map.values(matching) |> Enum.uniq() |> length()
end
end