Packages
fixpoint
0.17.6
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/constraints/all_different/utils_test.exs
defmodule CPSolverTest.Constraint.AllDifferent.Utils do
use ExUnit.Case, async: false
alias CPSolver.Propagator.AllDifferent.Utils, as: AllDiffUtils
describe "Forward checking" do
alias CPSolver.IntVariable, as: Variable
test "cascading" do
domains = [1, 1..2, 1..3, 1..4, 1..5]
vars = Enum.map(Enum.shuffle(domains), fn d -> Variable.new(d) end)
{unfixed_indices, fixed_values} = AllDiffUtils.forward_checking(vars)
assert MapSet.size(fixed_values) == length(vars)
## Everything is fixed
assert Enum.empty?(unfixed_indices)
assert Enum.all?(vars, fn var -> Variable.fixed?(var) end)
## AllDifferent check
assert MapSet.new(vars, fn var -> Variable.min(var) end) |> MapSet.size() == length(vars)
end
test "pigeonhole" do
domains = [1..2, 1..2, 1..2]
vars = Enum.map(Enum.shuffle(domains), fn d -> Variable.new(d) end)
{unfixed_indices, fixed_values} = AllDiffUtils.forward_checking(vars)
## FWC does not reduce if no fixed variables
assert MapSet.size(unfixed_indices) == length(vars)
assert Enum.empty?(fixed_values)
## Trigger reduction by fixing one of the variables
Variable.fix(Enum.random(vars), Enum.random(1..2))
assert catch_throw(:fail = AllDiffUtils.forward_checking(vars))
end
test "reuse" do
# An example from Zhang
domains = [1, 1..2, 1..4, [1, 2, 4, 5]]
vars = Enum.map(domains, fn d -> Variable.new(d) end)
{unfixed_indices, fixed_values} = AllDiffUtils.forward_checking(vars)
## First 2 variables fixed with values 1 and 2
assert unfixed_indices == MapSet.new([2, 3])
assert fixed_values == MapSet.new([1, 2])
## Run FWC again with the data from previous run - no effect
assert {unfixed_indices, fixed_values} == AllDiffUtils.forward_checking(vars, unfixed_indices, fixed_values)
## Fix and run FWC again with previous results
##
## domain(var3) = [3,4]; domain(var4) = [4,5]
## Fix shared value (4) for any of the unfixed variables
Variable.fix(Enum.at(vars, Enum.random([2,3])), 4)
{unfixed_indices2, _fixed_values2} = AllDiffUtils.forward_checking(vars, unfixed_indices, fixed_values)
## Everything is fixed
assert Enum.empty?(unfixed_indices2)
assert Enum.all?(vars, fn var -> Variable.fixed?(var) end)
end
end
describe "Component locator" do
test "build and locate" do
vertices = MapSet.new(1..10)
components = Enum.map([[1, 3, 5, 7, 9], [2, 4, 6, 8]], fn c -> MapSet.new(c) end)
component_locator = AllDiffUtils.build_component_locator(vertices, components)
assert AllDiffUtils.get_component(component_locator, 1) == hd(components)
assert AllDiffUtils.get_component(component_locator, 4) == List.last(components)
refute AllDiffUtils.get_component(component_locator, 10)
end
end
end