Packages
fixpoint
0.8.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_fwc_test.exs
defmodule CPSolverTest.Propagator.AllDifferent.FWC do
use ExUnit.Case
describe "Propagator filtering" do
alias CPSolver.ConstraintStore
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Variable.Interface
alias CPSolver.Propagator
alias CPSolver.Propagator.AllDifferent.FWC
test "maintains the list of unfixed variables" do
x =
Enum.map([{"x1", 0..5}, {"x2", 1..4}, {"x3", 0..5}, {"x4", 4}, {"x5", 5}], fn {name, d} ->
Variable.new(d, name: name)
end)
{:ok, x_vars, _store} = ConstraintStore.create_store(x)
[x1_var, x2_var, x3_var, _x4_var, _x5_var] = x_vars
## Initial state
##
fwc_propagator = FWC.new(x_vars)
filtering_results = Propagator.filter(fwc_propagator)
%{unfixed_vars: unfixed_vars} = filtering_results.state
## x1, x2 and x3 should be in unfixed_vars list
assert map_size(unfixed_vars) == 3
assert Enum.all?([x1_var, x2_var, x3_var], fn var ->
Map.has_key?(unfixed_vars, Interface.id(var))
end)
## The values of fixed variables (namely, 4 and 5) have been removed from unfixed variables
assert Enum.all?([x1_var, x2_var, x3_var], fn var -> Interface.max(var) == 3 end)
## Fixing one of the variables will remove the value it's fixed to from other variables
:fixed = Interface.fix(x1_var, 3)
fwc_propagator_step2 = Map.put(fwc_propagator, :state, filtering_results.state)
filtering_results2 = Propagator.filter(fwc_propagator_step2)
%{unfixed_vars: updated_unfixed_vars} = filtering_results2.state
## x1 had been fixed, and so is now removed from unfixed vars
assert map_size(updated_unfixed_vars) == 2
assert Interface.min(x2_var) == 1 && Interface.max(x2_var) == 2
assert Interface.min(x3_var) == 0 && Interface.max(x3_var) == 2
end
test "cascading filtering" do
## x1 is fixed, so the filtering removes 1 from all other variables.
## This makes x2 fixed, which in turn triggers a removal of 2 from x3 to x5 etc.
## Eventually all variables become fixed, and this will take a single filtering call.
##
x =
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)
{:ok, x_vars, _store} = ConstraintStore.create_store(x)
fwc_propagator = FWC.new(x_vars)
%{changes: changes} = Propagator.filter(fwc_propagator)
## x1 was already fixed; the filtering fixed the rest
assert map_size(changes) == length(x_vars) - 1
assert Enum.all?(Map.values(changes), fn change -> change == :fixed end)
assert Enum.all?(x_vars, &Interface.fixed?/1)
## Consequent filtering does not result in more changes and/or failures
%{changes: nil} = Propagator.filter(fwc_propagator)
assert Enum.all?(x_vars, &Interface.fixed?/1)
end
end
end