Packages
fixpoint
0.8.21
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/space/space_propagation_test.exs
defmodule CPSolverTest.SpacePropagation do
use ExUnit.Case
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Propagator.NotEqual
alias CPSolver.ConstraintStore
alias CPSolver.Space.Propagation
alias CPSolver.Propagator
alias CPSolver.Propagator.ConstraintGraph
test "Propagation on stable space" do
%{
propagators: propagators,
variables: [_x, y, _z] = variables,
constraint_graph: graph,
store: store
} = stable_setup()
{:stable, constraint_graph} = Propagation.run(propagators, graph, store)
assert Graph.num_vertices(constraint_graph) == 3
assert [y] ==
Enum.filter(variables, fn var ->
Graph.has_vertex?(constraint_graph, {:variable, var.id})
end)
## In stable state, variables referenced in constraint graph are unfixed.
refute Variable.fixed?(y)
propagators_from_graph =
Enum.flat_map(
Graph.vertices(constraint_graph),
fn
{:propagator, id} -> [ConstraintGraph.get_propagator(constraint_graph, id)]
_ -> []
end
)
assert length(propagators_from_graph) == 2
propagator_vars_in_graph =
Enum.map(propagators_from_graph, fn %{mod: NotEqual, args: vars} = _v ->
Enum.map(vars, fn v -> v.name end)
end)
## Both propagators in constraint graph have "y" variable
assert Enum.all?(propagator_vars_in_graph, fn vars -> "y" in vars end)
end
test "Propagation on solvable space" do
%{propagators: propagators, variables: variables, constraint_graph: graph, store: store} =
solved_setup()
refute Enum.all?(variables, fn var -> Variable.fixed?(var) end)
assert :solved == Propagation.run(propagators, graph, store)
assert Enum.all?(variables, fn var -> Variable.fixed?(var) end)
end
test "Propagation on failed space" do
%{propagators: propagators, constraint_graph: graph, store: store} = fail_setup()
assert :fail == Propagation.run(propagators, graph, store)
end
test "Propagation pass" do
x = 1..1
y = 1..2
z = 1..3
%{propagators: propagators, constraint_graph: graph, store: store} = space_setup(x, y, z)
{scheduled_propagators, reduced_graph} = Propagation.propagate(propagators, graph, store)
## Propagators are not being rescheduled
## as a result of their own filtering (idempotency).
##
## Only NotEqual(y, z) is rescheduled.
## Explanation:
## - NotEqual(x, y) changes y => schedules NotEqual(y,z);
## - NotEqual(x, z) changes z => schedules NotEqual(y,z);
## - NotEqual(y, z) changes z and/or y (if not called first) as a result of it's own filtering.
## So, at no point NotEqual(x, y) and NotEqual(x, z) are being rescheduled.
[not_equal_y_z_reference] = MapSet.to_list(scheduled_propagators)
not_equal_y_z = ConstraintGraph.get_propagator(reduced_graph, not_equal_y_z_reference)
assert not_equal_y_z.mod == NotEqual
assert not_equal_y_z.name == "y != z"
end
defp stable_setup() do
x = 1..1
y = -5..5
z = 0..1
space_setup(x, y, z)
end
defp solved_setup() do
x = 1..1
y = 0..2
z = 0..1
space_setup(x, y, z)
end
defp fail_setup() do
x = 1..1
y = 0..1
z = 0..1
space_setup(x, y, z)
end
defp space_setup(x, y, z) do
variables =
Enum.map([{x, "x"}, {y, "y"}, {z, "z"}], fn {d, name} -> Variable.new(d, name: name) end)
{:ok, [x_var, y_var, z_var] = bound_vars, store} =
ConstraintStore.create_store(variables)
propagators =
Enum.map(
[{x_var, y_var, "x != y"}, {y_var, z_var, "y != z"}, {x_var, z_var, "x != z"}],
fn {v1, v2, name} -> Propagator.new(NotEqual, [v1, v2], name: name) end
)
graph = ConstraintGraph.create(propagators)
{updated_graph, _bound_propagators} = ConstraintGraph.update(graph, bound_vars)
%{
propagators: propagators,
variables: bound_vars,
constraint_graph: updated_graph,
store: store
}
end
end