Packages
fixpoint
0.8.21
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, constraint_graph, store) when is_list(propagators) do
propagators
|> run_impl(constraint_graph, store)
|> finalize(propagators, store)
end
defp run_impl(propagators, constraint_graph, store) do
case propagate(propagators, constraint_graph, store) do
:fail ->
:fail
{scheduled_propagators, reduced_graph} ->
(MapSet.size(scheduled_propagators) == 0 && reduced_graph) ||
run_impl(scheduled_propagators, reduced_graph, store)
end
end
@spec propagate(map(), Graph.t(), map()) ::
:fail | {map(), Graph.t()} | {:changes, 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) when is_list(propagators) do
propagators
|> Map.new(fn p -> {p.id, p} end)
|> propagate(graph, store)
end
def propagate(%MapSet{} = propagator_ids, graph, store) do
Map.new(propagator_ids, fn p_id -> {p_id, ConstraintGraph.get_propagator(graph, p_id)} end)
|> propagate(graph, store)
end
def propagate(propagators, graph, store) when is_map(propagators) do
propagators
|> reorder()
|> Task.async_stream(
fn {p_id, p} ->
{p_id, Propagator.filter(p, store: store)}
end,
## TODO: make it an option
##
max_concurrency: 1
)
|> Enum.reduce_while({MapSet.new(), graph}, fn {:ok, {p_id, res}}, {scheduled, g} = _acc ->
case res do
:fail ->
{:halt, :fail}
:stable ->
{:cont, {unschedule(scheduled, p_id), g}}
%{changes: nil, active?: active?} ->
{:cont, {unschedule(scheduled, p_id), maybe_remove_propagator(g, p_id, active?)}}
%{changes: changes} = filtering_results ->
case update_propagator(g, p_id, filtering_results) do
:fail ->
{:halt, :fail}
updated_graph ->
{updated_graph, scheduled_by_propagator} =
schedule_by_propagator(changes, updated_graph)
{:cont, {reschedule(scheduled, p_id, scheduled_by_propagator), updated_graph}}
end
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 reschedule(current_schedule, p_id, scheduled_by_propagator) do
current_schedule
|> MapSet.union(scheduled_by_propagator)
|> unschedule(p_id)
end
## Returns set of propagator ids scheduled as a result of domain changes.
defp schedule_by_propagator(domain_changes, graph) do
{updated_graph, scheduled_propagators} =
domain_changes
|> Enum.reduce({graph, MapSet.new()}, fn {var_id, domain_change}, {g, propagators} ->
{maybe_remove_variable(g, var_id, domain_change),
MapSet.union(
propagators,
MapSet.new(ConstraintGraph.get_propagator_ids(g, var_id, domain_change))
)}
end)
{updated_graph, scheduled_propagators}
end
defp maybe_remove_propagator(graph, _propagator_id, _active?) do
## TODO: reintroduce removing passive propagators
## There is a bigger problem as to what to do with unfixed variables
## when no active propagators left.
# (active? && graph) || ConstraintGraph.remove_propagator(graph, propagator_id)
graph
end
## Update propagator
## Do not update if passive
defp update_propagator(graph, _propagator_id, %{active?: false} = _filtering_results) do
graph
end
defp update_propagator(graph, propagator_id, %{changes: changes, active?: true, state: state}) do
case ConstraintGraph.get_propagator(graph, propagator_id) do
nil ->
graph
p ->
Map.put(p, :state, state)
|> Propagator.update(changes)
|> then(fn updated_propagator ->
ConstraintGraph.update_propagator(graph, propagator_id, updated_propagator)
end)
end
end
defp finalize(:fail, _propagators, _store) do
:fail
end
## At this point, the space is either solved or stable.
defp finalize(%Graph{} = residual_graph, propagators, store) do
if Enum.empty?(Graph.edges(residual_graph)) do
(checkpoint(propagators, store) && :solved) || :fail
else
{:stable, remove_entailed_propagators(residual_graph, propagators)}
end
end
defp checkpoint(propagators, store) do
Enum.reduce_while(propagators, true, fn p, acc ->
case Propagator.filter(p, store: store) do
:fail -> {:halt, false}
_ -> {:cont, acc}
end
end)
end
defp remove_entailed_propagators(graph, propagators) do
Enum.reduce(propagators, graph, fn p, g ->
p_vertex = ConstraintGraph.propagator_vertex(p.id)
case Graph.neighbors(g, p_vertex) do
[] -> ConstraintGraph.remove_propagator(g, p.id)
_connected_vars -> g
end
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.
## In general, arrange by the number of fixed variables?
##
defp reorder(propagators) do
propagators
end
end