Packages
fixpoint
0.9.7
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/afc_test.exs
defmodule CPSolverTest.Search.AFC do
use ExUnit.Case
alias CPSolver.Search.VariableSelector.AFC, as: AFC
alias CPSolver.Space
import CPSolver.Test.Helpers
describe "AFC search strategy" do
alias CPSolver.Shared
test "initialization from top space" do
space = build_space()
shared = Space.get_shared(space)
decay = :rand.uniform()
AFC.initialize(space, decay)
assert decay == AFC.get_decay(shared)
afc_table_ref = AFC.get_afc_table(shared)
propagator_refs = Enum.map(space.propagators, fn p -> p.id end)
assert Enum.all?(
:ets.tab2list(afc_table_ref),
fn {p_ref, {1, 0}} -> p_ref in propagator_refs end
)
end
test "get AFC record for propagator" do
space = build_space()
AFC.initialize(space, :rand.uniform())
propagator_refs = Enum.map(space.propagators, fn p -> p.id end)
shared = Space.get_shared(space)
assert Enum.all?(propagator_refs, fn p_id ->
{1, 0} = AFC.get_afc_record(p_id, shared)
end)
end
test "update propagator AFC" do
space = build_space()
shared = Space.get_shared(space)
decay = :rand.uniform()
AFC.initialize(space, decay)
[p1, p2, p3 | _rest] = Enum.map(space.propagators, fn p -> p.id end)
## Simulate propagator failure for 'p1' propagator
Shared.add_failure(shared, {:fail, p1})
{p1_afc, 1} = AFC.get_afc_record(p1, shared)
assert p1_afc == 2
## Manually decay p2
AFC.update_afc(p2, shared, false)
## AFC record advances to decayed value and the last global failure count
assert {decay, 1} == AFC.get_afc_record(p2, shared)
## Simulate propagator failure for 'p2' propagator
Shared.add_failure(shared, {:fail, p2})
## Trigger update for 'p2'
## AFC record is incremented by 1, the last global failure count is updated
assert {decay + 1, 2} == AFC.get_afc_record(p2, shared)
## Compute AFC for 'p1' again, it should be decayed once.
assert {p1_afc * decay, 2} == AFC.propagator_afc(p1, shared)
## Compute AFC for 'p3'. It should be decayed twice from initial value of 1.
assert {decay * decay, 2} == AFC.propagator_afc(p3, shared)
end
test "Calculate variable AFC" do
space = build_space()
shared = Space.get_shared(space)
decay = :rand.uniform()
AFC.initialize(space, decay)
variables = space.variables
## The propagators in the space setup are:
## X != Y, X != Z, Y != Z
##
## That is, each variable participates in 2 propagators.
## 1. The initial AFC for every variable should be equal to 2.
Enum.each(variables, fn var -> assert 2 == AFC.variable_afc(var, shared) end)
[p1, _p2, _p3] = space.propagators
## 2. Fail the propagator x != y
## This should increment AFCs for variables x and y and decay AFC for variable z
assert Enum.map(p1.args, fn arg -> arg.name end) == ["x", "y"]
Shared.add_failure(shared, {:fail, p1.id})
[var1, var2, var3] = space.variables
assert var1.name == "x" && var2.name == "y" && var3.name == "z"
## Variables `x` and `y` participate in 1 failed (x != y) and 1 non-failed propagator.
## Hence the AFC for both of these variables is (2 + decay)
assert 2 + decay == AFC.variable_afc(var1, shared)
assert 2 + decay == AFC.variable_afc(var2, shared)
## Both propagators variable `z` have not failed, both of them decayed.
## So AFC for `z` is (2 * decay)
assert 2 * decay == AFC.variable_afc(var3, shared)
end
test "Calculate multiple variable AFCs" do
space = build_space()
shared = Space.get_shared(space)
decay = :rand.uniform()
AFC.initialize(space, decay)
variables = space.variables
## The propagators in the space setup are:
## X != Y, X != Z, Y != Z
##
## That is, each variable participates in 2 propagators.
## 1. The initial AFC for every variable should be equal to 2.
assert Enum.all?(AFC.variable_afcs(variables, shared), fn {var, afc_value} ->
2 == afc_value
end)
[p1, _p2, _p3] = space.propagators
# ## 2. Fail the propagator x != y
# ## This should increment AFCs for variables x and y and decay AFC for variable z
assert Enum.map(p1.args, fn arg -> arg.name end) == ["x", "y"]
Shared.add_failure(shared, {:fail, p1.id})
[{var1, afc1}, {var2, afc2}, {var3, afc3}] =
AFC.variable_afcs(variables, shared) |> Enum.sort_by(fn {var, _afc} -> var.name end)
assert var1.name == "x" && var2.name == "y" && var3.name == "z"
# ## Variables `x` and `y` participate in 1 failed (x != y) and 1 non-failed propagator.
# ## Hence the AFC for both of these variables is (2 + decay)
assert 2 + decay == afc1
assert 2 + decay == afc2
# ## Both propagators variable `z` have not failed, both of them decayed.
# ## So AFC for `z` is (2 * decay)
assert 2 * decay == afc3
end
defp build_space() do
shared = Shared.init_shared_data(space_threads: 4)
space_setup(0..5, 0..5, 0..5)
|> Map.put(:opts, solver_data: shared)
|> tap(fn space ->
Space.put_shared(space, :initial_constraint_graph, space.constraint_graph)
end)
end
end
end