Packages
fixpoint
0.8.4
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
lib/solver/constraints/propagators/element2d.ex
defmodule CPSolver.Propagator.Element2D do
use CPSolver.Propagator
import CPSolver.Utils
@moduledoc """
The propagator for Element2D constraint.
"""
def new(array2d, x, y, z) do
new([array2d, x, y, z])
end
@impl true
def variables([_array2d, x, y, z]) do
[
set_propagate_on(x, :domain_change),
set_propagate_on(y, :domain_change),
set_propagate_on(z, :domain_change)
]
end
defp initial_state([[], _x, _y, _z]) do
throw(:fail)
end
defp initial_state([array2d, x, y, z]) do
num_rows = length(array2d)
num_cols = length(hd(array2d))
initial_reduction(array2d, x, y, z, num_rows, num_cols)
state = build_state(array2d, x, y, z, num_rows, num_cols)
maybe_reduce_domains(x, y, z, state)
end
def build_state(array2d, x, y, z, num_rows, num_cols) do
## Build a graph.
## Three sets of vertices: ([{:z, value}], [{:x, value}], [{:y, value}])
## with edges from {:z, z_value} to {:x, x_value},
## where z_value is present in x_value row of array2d.
## Likewise, with edges from {:z, z_value} to {:y, y_value},
## where z_value is present in y_value column of array2d.
for i <- 0..(num_rows - 1), j <- 0..(num_cols - 1), reduce: Graph.new() do
acc ->
if contains?(x, i) && contains?(y, j) do
table_value = Enum.at(array2d, i) |> Enum.at(j)
if contains?(z, table_value) do
acc
|> Graph.add_edge({:z, table_value}, {:x, i}, label: {:y, j})
|> Graph.add_edge({:z, table_value}, {:y, j}, label: {:x, i})
else
acc
end
else
acc
end
end
end
## Try to reduce some domains
# |> then(fn maps ->
# maybe_reduce_domains(x, y, z, maps)
# end)
defp initial_reduction(array2d, x, y, z, num_rows, num_cols) do
# x and y are indices in array2d,
# so we trim D(x) and D(y) accordingly.
removeBelow(x, 0)
removeAbove(x, num_rows - 1)
removeBelow(y, 0)
removeAbove(y, num_cols - 1)
## D(z) is bounded by min and max of the array2d
{arr_min, arr_max} = array2d_min_max(array2d)
removeAbove(z, arr_max)
removeBelow(z, arr_min)
end
defp maybe_reduce_domains(x, y, z, %Graph{} = graph) do
{updated_graph, changed?} =
Enum.reduce(Graph.vertices(graph), {graph, false}, fn
{:z, _} = v, acc ->
maybe_remove_vertex(v, z, acc)
{:x, _} = v, acc ->
maybe_remove_vertex(v, x, acc)
{:y, _} = v, acc ->
maybe_remove_vertex(v, y, acc)
end)
## Repeat if any reductions were made
if changed? do
maybe_reduce_domains(x, y, z, updated_graph)
else
updated_graph
end
end
defp maybe_remove_vertex(
{_signature, value} = vertex,
variable,
{graph, _changed?} = acc,
removal_condition \\ fn graph, vertex -> Graph.degree(graph, vertex) == 0 end
) do
cond do
!contains?(variable, value) ->
{remove_vertex(graph, vertex), true}
removal_condition.(graph, vertex) ->
remove(variable, value)
{remove_vertex(graph, vertex), true}
true ->
acc
end
end
defp remove_vertex(graph, {:z, _value} = vertex) do
Graph.delete_vertex(graph, vertex)
end
defp remove_vertex(graph, {signature, _value} = vertex) when signature in [:x, :y] do
graph
|> Graph.delete_vertex(vertex)
## We delete all edges related to this vertex (that is, labelled {:signature, value})
|> then(fn graph ->
graph
|> Graph.edges()
|> Enum.reduce(
graph,
fn edge, acc ->
(edge.label == vertex && Graph.delete_edge(acc, edge.v1, edge.v2, edge.label)) ||
acc
end
)
end)
end
@impl true
def filter(args) do
filter(args, initial_state(args))
end
def filter(args, nil) do
filter(args, initial_state(args))
end
@impl true
def filter(args, state) do
updated_state = filter_impl(args, state)
if Graph.vertices(updated_state) |> Enum.empty?() do
:fail
else
{:state, updated_state}
end
end
defp filter_impl([_array2d, x, y, z], state) do
maybe_reduce_domains(x, y, z, state)
end
end