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/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(Graph.components(reduced_value_graph))
assert 6 == length(Graph.edges(reduced_value_graph))
assert 9 == length(Graph.vertices(reduced_value_graph))
# The value graph is split into 2 single-edge components and one component with Γ(A) + A vertices
assert Enum.map(Graph.components(reduced_value_graph), fn component -> length(component) end) |> Enum.sort() == [2, 2, 5]
# Single-edge SCCs are removed, one left is the one with reduced t2-type edges
assert state.components == 1
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