Packages
fixpoint
0.12.5
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/propagators/all_different/all_different_dc_fast_test.exs
defmodule CPSolverTest.Propagator.AllDifferent.DC.Fast do
use ExUnit.Case
# alias CPSolver.ConstraintStore
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Variable.Interface
# alias CPSolver.Propagator
alias CPSolver.Propagator.AllDifferent.DC.Fast
describe "Reduction algoritm (Zhang et al. paper example" do
test "reduction" do
domains = [1, 1..2, 1..4, [1, 2, 4, 5]]
[_x0, x1, x2, x3] =
vars =
Enum.map(Enum.with_index(domains, 0), fn {d, idx} ->
Variable.new(d, name: "x#{idx}")
end)
state = Fast.initial_reduction(vars)
reduced_value_graph = state[:value_graph]
assert Interface.fixed?(x1) && Interface.min(x1) == 2
assert Interface.min(x2) == 3 && Interface.max(x2) == 4
assert Interface.min(x3) == 4 && Interface.max(x3) == 5
## Reduced value graph consists of 3 components, as per paper
assert 3 == length(BitGraph.Algorithms.components(reduced_value_graph))
## the number of edges is 6 (Figure 2 of the paper)
assert 6 ==
Enum.reduce(BitGraph.vertices(reduced_value_graph), 0, fn v, sum_acc -> sum_acc + BitGraph.out_degree(reduced_value_graph, v) end)
assert 9 == MapSet.size(BitGraph.vertices(reduced_value_graph))
# The value graph is split into 2 single-edge components and one component with Γ(A) + A vertices
assert Enum.map(BitGraph.Algorithms.components(reduced_value_graph), fn component -> MapSet.size(component) end) |> Enum.sort() == [2, 2, 5]
# Single-edge components are removed, one left is the one with reduced t1-type edges (variables x2 and x3)
assert MapSet.size(state.components) == 1
assert hd(MapSet.to_list(state.components)) == MapSet.new([2, 3])
end
test "cascading" do
[x2, _x1, x3, x4, x5] =
vars =
Enum.map([{"x2", 1..2}, {"x1", 1}, {"x3", 1..3}, {"x4", 1..4}, {"x5", 1..5}], fn {name, d} ->
Variable.new(d, name: name)
end)
Fast.initial_reduction(vars)
## all variables are fixed
assert Interface.fixed?(x2) && Interface.min(x2) == 2
assert Interface.fixed?(x3) && Interface.min(x3) == 3
assert Interface.fixed?(x4) && Interface.min(x4) == 4
assert Interface.fixed?(x5) && Interface.min(x5) == 5
end
test "inconsistency (pigeonhole)" do
domains = List.duplicate(1..3, 4)
vars =
Enum.map(domains, fn d -> Variable.new(d) end)
assert catch_throw(Fast.initial_reduction(vars)) == :fail
end
end
describe "Filtering" do
alias CPSolver.Propagator
test "reduction" do
domains = [1, 1..2, 1..4, [1, 2, 4, 5]]
[_x0, x1, x2, x3] =
vars =
Enum.map(Enum.with_index(domains, 0), fn {d, idx} ->
Variable.new(d, name: "x#{idx}")
end)
dc_propagator = Propagator.new(Fast, vars)
%{active?: true, state: state1} =
Propagator.filter(dc_propagator)
## Variable filtering
assert Interface.fixed?(x1) && Interface.min(x1) == 2
assert Interface.min(x2) == 3 && Interface.max(x2) == 4
assert Interface.min(x3) == 4 && Interface.max(x3) == 5
## More filtering
domain_change = Interface.fix(x2, 4)
assert %{active?: false} =
Propagator.filter(Map.put(dc_propagator, :state, state1), changes: %{2 => domain_change})
assert Interface.fixed?(x2) && Interface.min(x2) == 4
assert Interface.fixed?(x3) && Interface.min(x3) == 5
end
end
end