Packages
fixpoint
0.7.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/search/search_strategy_test.exs
defmodule CPSolverTest.Search.FirstFail do
use ExUnit.Case
describe "First-fail search strategy" do
alias CPSolver.ConstraintStore
alias CPSolver.IntVariable, as: Variable
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search.Strategy, as: SearchStrategy
test ":first_fail and :indomain_min" do
v0_values = 0..0
v1_values = 1..10
# This domain is the smallest among unfixed
v2_values = 0..5
v3_values = 1..1
v4_values = -5..5
values = [v0_values, v1_values, v2_values, v3_values, v4_values]
variables = Enum.map(values, fn d -> Variable.new(d) end)
{:ok, bound_vars, store} = ConstraintStore.create_store(variables)
{localized_vars, _} = CPSolver.Utils.localize_variables(bound_vars)
# first_fail chooses unfixed variable
selected_variable = SearchStrategy.select_variable(localized_vars, :first_fail)
v2_var = Enum.at(bound_vars, 2)
assert selected_variable.id == v2_var.id
var_domain = ConstraintStore.domain(store, selected_variable)
min_val = Domain.min(var_domain)
# indomain_min splits domain of selected variable into min and the rest of the domain
assert SearchStrategy.partition(selected_variable, :indomain_min) ==
{:ok, [min_val, Domain.new(List.delete(Enum.to_list(v2_values), 0))]}
end
test "first_fail fails if no unfixed variables" do
v0_values = 0..0
v1_values = 1..1
v2_values = -2..-2
v3_values = 1..1
v4_values = 5..5
values = [v0_values, v1_values, v2_values, v3_values, v4_values]
variables = Enum.map(values, fn d -> Variable.new(d) end)
{:ok, _bound_vars, _store} = ConstraintStore.create_store(variables)
assert catch_throw(SearchStrategy.select_variable(variables, :first_fail)) ==
SearchStrategy.all_vars_fixed_exception()
end
test "branch creation" do
v0_values = 0..0
v1_values = 1..10
# This domain is the smallest among unfixed
v2_values = 0..5
v3_values = 1..1
v4_values = -5..5
values = [v0_values, v1_values, v2_values, v3_values, v4_values]
variables = Enum.map(values, fn d -> Variable.new(d) end)
{:ok, bound_vars, _store} = ConstraintStore.create_store(variables)
[b_left, b_right] =
branches = SearchStrategy.branch(bound_vars, {:first_fail, :indomain_min})
refute b_left == b_right
## Each branch has the same number of variables, as the original list of vars
assert Enum.all?(branches, fn branch -> length(branch) == length(variables) end)
## Left branch contains v2 variable fixed at 0
assert Enum.at(b_left, 2)
|> Map.get(:domain)
|> then(fn domain -> Domain.size(domain) == 1 && Domain.min(domain) == 0 end)
## Right branch contains v2 variable with 0 removed
refute Enum.at(b_right, 2) |> Map.get(:domain) |> Domain.contains?(0)
end
end
end