Packages
fixpoint
0.5.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
lib/solver/space/propagation.ex
defmodule CPSolver.Space.Propagation do
alias CPSolver.Propagator.ConstraintGraph
alias CPSolver.Variable
alias CPSolver.Propagator
defp propagate(map, _store) when map_size(map) == 0 do
:no_changes
end
@spec propagate(map(), map()) :: :fail | :no_changes | {:changes, map()}
defp propagate(propagators, store) do
propagators
|> Task.async_stream(fn {_ref, p} -> Propagator.filter(p, store: store) end)
|> Enum.reduce_while(%{}, fn {:ok, res}, acc ->
case res do
{:changed, change} -> {:cont, Map.merge(acc, change)}
:stable -> {:cont, acc}
{:fail, _var} -> {:halt, :fail}
end
end)
|> then(fn
:fail ->
:fail
changes when map_size(changes) > 0 ->
{:changed, changes}
_no_changes ->
:no_changes
end)
end
def run(propagators, variables, store \\ nil)
def run(propagators, variables, store) when is_list(propagators) do
propagators
|> Enum.map(fn p -> {make_ref(), p} end)
|> Map.new()
|> run(variables, store)
end
def run(propagators, variables, store) when is_map(propagators) and map_size(propagators) > 0 do
run(propagators, variables, ConstraintGraph.create(propagators), store)
end
def run(propagators, variables, constraint_graph, store) when is_map(propagators) do
propagators
|> run_impl(constraint_graph, store)
|> finalize(constraint_graph, propagators, variables)
end
defp run_impl(propagators, _constraint_graph, _store) when map_size(propagators) == 0 do
:no_changes
end
defp run_impl(propagators, constraint_graph, store) do
case propagate(propagators, store) do
:fail ->
:fail
:no_changes ->
:no_changes
{:changed, changes} ->
wakeup(changes, constraint_graph)
|> run_impl(constraint_graph, store)
end
end
defp finalize(:fail, _constraint_graph, _propagators, _variables) do
:fail
end
## At this point, the space is either solved or stable.
## Reduce constraint graph and interpret the result.
defp finalize(:no_changes, constraint_graph, propagators, variables) do
remove_fixed_variables(constraint_graph, variables)
|> remove_entailed_propagators()
|> then(fn {removed_propagator_ids, residue} ->
(Graph.vertices(residue) == [] && :solved) ||
{:stable, residue, Map.drop(propagators, removed_propagator_ids)}
end)
end
## Wake up propagators based on the changes
defp wakeup(changes, constraint_graph) when is_map(changes) do
changes
|> Enum.uniq()
|> Enum.reduce([], fn {var_id, change}, acc ->
acc ++ ConstraintGraph.get_propagator_ids(constraint_graph, var_id, change)
end)
|> Enum.uniq()
|> Enum.map(fn propagator_id ->
ConstraintGraph.get_propagator(constraint_graph, propagator_id)
end)
end
defp remove_fixed_variables(graph, vars) do
Enum.reduce(vars, graph, fn v, acc ->
if Variable.fixed?(v) do
ConstraintGraph.remove_variable(acc, v.id)
else
acc
end
end)
end
defp remove_entailed_propagators(constraint_graph) do
Enum.reduce(Graph.vertices(constraint_graph), {[], constraint_graph}, fn
{:propagator, id} = v, {removed_propagator_ids, graph} = acc ->
(Graph.neighbors(graph, v) == [] &&
{[id | removed_propagator_ids], Graph.delete_vertex(graph, v)}) || acc
_v, acc ->
acc
end)
end
end