Packages
fixpoint
0.8.32
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
import CPSolver.Common
require Logger
def run(constraint_graph, store, changes \\ %{})
def run(%Graph{} = constraint_graph, store, changes) do
constraint_graph
|> get_propagators()
|> then(fn propagators ->
run_impl(propagators, constraint_graph, store, changes, reset?: true)
|> finalize()
end)
end
defp get_propagators(constraint_graph) do
constraint_graph
|> Graph.vertices()
## Get %{id => propagator} map
|> Enum.flat_map(fn {:propagator, p_id} ->
[ConstraintGraph.get_propagator(constraint_graph, p_id)]
_ -> []
end)
end
defp run_impl(propagators, constraint_graph, store, domain_changes, opts) do
case propagate(propagators, constraint_graph, store, domain_changes, opts) do
:fail ->
:fail
{scheduled_propagators, reduced_graph, new_domain_changes} ->
(MapSet.size(scheduled_propagators) == 0 && reduced_graph) ||
run_impl(scheduled_propagators, reduced_graph, store, new_domain_changes, reset?: false)
end
end
def propagate(propagators, graph, store) do
propagate(propagators, graph, store, [])
end
def propagate(propagators, graph, store, opts) do
propagate(propagators, graph, store, Map.new(), opts)
end
@spec propagate(map(), Graph.t(), map(), map(), Keyword.t()) ::
:fail | {map(), Graph.t(), map()}
@doc """
A single 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, domain_changes, opts) when is_list(propagators) do
propagators
|> Map.new(fn p -> {p.id, p} end)
|> propagate(graph, store, domain_changes, opts)
end
def propagate(%MapSet{} = propagator_ids, graph, store, domain_changes, opts) do
Map.new(propagator_ids, fn p_id -> {p_id, ConstraintGraph.get_propagator(graph, p_id)} end)
|> propagate(graph, store, domain_changes, opts)
end
def propagate(propagators, graph, store, domain_changes, opts) when is_map(propagators) do
propagators
|> reorder()
|> Enum.reduce_while(
{MapSet.new(), graph, Map.new()},
fn {p_id, p}, {scheduled_acc, g_acc, changes_acc} = _acc ->
res = Propagator.filter(p,
store: store,
reset?: opts[:reset?],
changes: Map.get(domain_changes, p_id)
)
case res do
{:filter_error, error} ->
throw({:error, {:filter_error, error}})
:fail ->
{:halt, :fail}
:stable ->
{:cont, {unschedule(scheduled_acc, p_id), g_acc, changes_acc}}
%{changes: no_changes, active?: active?} when no_changes in [nil, %{}] ->
{:cont,
{unschedule(scheduled_acc, p_id),
maybe_remove_propagator(g_acc, p_id, active?), changes_acc}}
%{changes: new_changes, state: state} ->
{updated_graph, updated_scheduled, updated_changes} =
update_schedule(scheduled_acc, changes_acc, new_changes, g_acc)
{:cont,
{updated_scheduled |> unschedule(p_id),
ConstraintGraph.update_propagator(updated_graph, p_id, Map.put(p, :state, state)),
updated_changes}}
end
end
)
end
## Note: we do not reschedule a propagator that was the source of domain changes,
## as we assume idempotence (that is, running a 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 update_schedule(current_schedule, current_changes, new_domain_changes, graph) do
{updated_graph, scheduled_propagators, cumulative_domain_changes} =
new_domain_changes
|> Enum.reduce(
{graph, current_schedule, current_changes},
fn {var_id, domain_change} = change, {g_acc, propagators_acc, changes_acc} ->
propagator_ids =
ConstraintGraph.get_propagator_ids(g_acc, var_id, domain_change)
{maybe_remove_variable(g_acc, var_id, domain_change),
MapSet.union(
propagators_acc,
MapSet.new(Map.keys(propagator_ids))
), propagator_changes(propagator_ids, change, changes_acc)}
end
)
{updated_graph, scheduled_propagators, cumulative_domain_changes}
end
## Remove passive propagator
defp maybe_remove_propagator(graph, propagator_id, active?) do
active? && graph || ConstraintGraph.remove_propagator(graph, propagator_id)
end
defp finalize(:fail) do
:fail
end
## At this point, the space is either solved or stable.
defp finalize(%Graph{} = residual_graph) do
if Enum.empty?(Graph.edges(residual_graph)) do
:solved
else
{:stable, residual_graph}
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 unschedule(scheduled_propagators, p_id) do
MapSet.delete(scheduled_propagators, p_id)
end
## TODO: possible reordering strategy
## for the next pass.
## Ideas:
## - Put to-be-entailed propagators first,
## so if they fail, it'd be early.
## - (extension of ^^) Order by the number of fixed variables
##
defp reorder(propagators) do
propagators
end
defp propagator_changes(propagator_ids, {_var_id, domain_change} = _change, changes_acc) do
Enum.reduce(
propagator_ids,
changes_acc,
fn {p_id, p_data}, acc ->
arg_position = p_data.arg_position
Map.update(acc, p_id, Map.new(%{arg_position => domain_change}), fn var_map ->
current_var_change = Map.get(var_map, arg_position)
Map.put(
var_map,
arg_position,
stronger_domain_change(current_var_change, domain_change)
)
end)
end
)
end
end