Packages
fixpoint
0.5.5
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.Propagator
def run(propagators, store \\ nil)
def run(propagators, store) when is_list(propagators) do
propagators
|> Enum.map(fn p -> {make_ref(), p} end)
|> Map.new()
|> run(store)
end
def run(propagators, store) when is_map(propagators) and map_size(propagators) > 0 do
run(propagators, ConstraintGraph.create(propagators), store)
end
def run(propagators, constraint_graph, store) when is_map(propagators) do
propagators
|> run_impl(constraint_graph, store)
|> finalize(propagators)
end
defp run_impl(scheduled_propagators, constraint_graph, _store)
when map_size(scheduled_propagators) == 0 do
constraint_graph
end
defp run_impl(propagators, constraint_graph, store) do
case propagate(propagators, constraint_graph, store) do
:fail ->
:fail
{scheduled_propagators, reduced_graph} ->
run_impl(scheduled_propagators, reduced_graph, store)
end
end
@spec propagate(map(), Graph.t(), map()) ::
:fail | {map(), Graph.t()} | {:changes, map()}
@doc """
One pass of propagation.
Produces the list (up to implementation) of propagators scheduled for the next pass.
Side effect: modifies the constraint graph.
The graph will be modified on every individual Propagator.filter/1, if the latter results in any domain changes.
"""
def propagate(propagators, graph, store) do
propagators
|> Task.async_stream(fn {p_id, p} ->
{p_id, Propagator.filter(p, store: store)}
end)
|> Enum.reduce_while({Map.new(), graph}, fn {:ok, {p_id, res}}, {scheduled, g} = acc ->
case res do
{:fail, _var} ->
{:halt, :fail}
:stable ->
{:cont, acc}
{:changed, changes} ->
{updated_graph, scheduled_by_propagator} = schedule(p_id, changes, g)
{:cont,
{
Map.merge(scheduled, scheduled_by_propagator),
updated_graph
}}
end
end)
end
## Note: we do not reschedule a propagator that was the source of domain changes,
## as we assume idempotence (that is, running propagator for the second time wouldn't change domains).
## We will probably introduce the option to be used in propagator implementations
## to signify that the propagator is not idempotent.
##
defp schedule(source_id, domain_changes, graph) do
{updated_graph, scheduled_propagators} =
domain_changes
|> Enum.reduce({graph, %{}}, fn {var_id, domain_change}, {g, propagators} ->
{maybe_remove_variable(g, var_id, domain_change),
Map.merge(
propagators,
Map.new(
ConstraintGraph.get_propagators(g, var_id, domain_change),
fn p -> {p.id, fix_propagator_variables(p, var_id, domain_change)} end
)
)}
end)
{updated_graph, Map.delete(scheduled_propagators, source_id)}
end
defp finalize(:fail, _propagators) do
:fail
end
## At this point, the space is either solved or stable.
defp finalize(%Graph{} = residue, propagators) do
(Graph.vertices(residue) == [] && :solved) ||
{:stable, residue, propagators_from_graph(residue, propagators)}
end
defp propagators_from_graph(graph, propagators) do
Enum.reduce(propagators, Map.new(), fn {p_id, p}, acc ->
(ConstraintGraph.get_propagator(graph, p_id) && Map.put(acc, p_id, p)) || acc
end)
end
defp maybe_remove_variable(graph, var_id, :fixed) do
ConstraintGraph.remove_variable(graph, var_id)
end
defp maybe_remove_variable(graph, _var_id, _domain_change) do
graph
end
defp fix_propagator_variables(propagator, var_id, :fixed) do
propagator
|> Map.update(:args, %{}, fn args ->
Enum.map(
args,
fn
%{id: id} = arg when id == var_id ->
Map.put(arg, :fixed?, true)
other ->
other
end
)
end)
end
defp fix_propagator_variables(propagator, _var_id, _domain_change) do
propagator
end
end