Packages
fixpoint
0.12.8
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/constraint_graph_test.exs
defmodule CPSolverTest.Propagator.ConstraintGraph do
use ExUnit.Case
require Logger
describe "Propagator graph" do
alias CPSolver.Propagator.ConstraintGraph
alias CPSolver.Constraint.AllDifferent.Binary, as: AllDifferent
alias CPSolver.Constraint
alias CPSolver.Propagator
alias CPSolver.IntVariable, as: Variable
alias CPSolver.DefaultDomain, as: Domain
import CPSolver.Utils
test "Build graph from AllDifferent constraint" do
graph = build_graph(AllDifferent, 3)
## Vertices: 3 propagators (x != y, y != z, x != z) and 3 variables
assert length(ConstraintGraph.vertices(graph)) == 6
## Edges: 2 per each propagator
assert length(ConstraintGraph.edges(graph)) == 6
## All edges are labeled with :fixed
Enum.all?(ConstraintGraph.edges(graph), fn edge -> assert edge.label.propagate_on == [:fixed] end)
## Make sure the propagators are properly bound to their variables
assert_propagator_domains(graph, 1..3)
end
test "Get propagators for the given variable and domain event" do
graph = build_graph(AllDifferent, 3)
variables =
ConstraintGraph.vertices(graph)
|> Enum.flat_map(fn
{:variable, v} -> [v]
_ -> []
end)
## For each variable, there are 2 propagators listening to ':fixed' domain change
Enum.all?(variables, fn var_id ->
assert map_size(ConstraintGraph.get_propagator_ids(graph, var_id, :fixed)) == 2
end)
end
test "Remove variables" do
graph = build_graph(AllDifferent, 3)
variables =
[v1, _v2, _v3] = get_variable_ids(graph)
assert graph |> ConstraintGraph.remove_variable(v1) |> ConstraintGraph.edges() |> length == 4
assert Enum.reduce(variables, graph, fn v, g ->
assert ConstraintGraph.vertices(g) != []
ConstraintGraph.remove_variable(g, v)
end)
|> ConstraintGraph.edges() == []
end
test "Update graph variables" do
graph = build_graph(AllDifferent, 3)
graph_variables = get_variables(graph)
new_variables =
Enum.map(graph_variables, fn v ->
Variable.copy(v) |> tap(fn c -> Variable.remove(c, 3) end)
end)
updated_graph = ConstraintGraph.update(graph, new_variables)
## The domains fo variables in the graph should be updated with domains of new variables
assert Enum.all?(
get_variables(updated_graph),
fn var ->
Domain.to_list(var.domain) == MapSet.new([1, 2])
end
)
## The propagators should be bound to new variables
assert_propagator_domains(updated_graph, 1..2)
end
defp build_graph(constraint_impl, n) do
domain = 1..n
variables = Enum.map(1..n, fn _i -> Variable.new(domain) end)
constraint = Constraint.new(constraint_impl, variables)
propagators = Constraint.constraint_to_propagators(constraint)
ConstraintGraph.create(propagators)
end
defp get_variable_ids(graph) do
ConstraintGraph.vertices(graph)
|> Enum.flat_map(fn
{:variable, v} -> [v]
_ -> []
end)
end
defp get_variables(graph) do
graph
|> get_variable_ids()
|> Enum.map(fn var_id -> ConstraintGraph.get_variable(graph, var_id) end)
end
defp assert_propagator_domains(graph, domain) do
propagators =
Enum.flat_map(
ConstraintGraph.vertices(graph),
fn
{:propagator, p_id} ->
[
ConstraintGraph.get_propagator(graph, p_id)
|> Propagator.bind(graph, :domain)
]
_ ->
[]
end
)
assert length(propagators) == 3
assert Enum.all?(
propagators,
fn p ->
Enum.all?(p.args, fn arg ->
is_integer(arg) ||
domain_values(arg) ==
MapSet.new(domain)
end)
end
)
end
end
end