Packages
fixpoint
0.6.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.Propagator
def run(propagators, store \\ nil)
def run(propagators, store) do
run(propagators, ConstraintGraph.create(propagators), store)
end
def run(propagators, constraint_graph, store) when is_list(propagators) do
propagators
|> run_impl(constraint_graph, store)
|> finalize(propagators)
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 """
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) 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)
|> Enum.reduce_while({MapSet.new(), graph}, fn {:ok, {p_id, res}}, {scheduled, g} = acc ->
case res do
{:fail, _var} ->
{:halt, :fail}
:fail ->
{:halt, :fail}
:stable ->
{:cont, acc}
{:changed, changes} ->
{updated_graph, scheduled_by_propagator} = schedule_by_propagator(changes, g)
{:cont,
{
reschedule(scheduled, p_id, 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 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_propagators(g, var_id, domain_change))
)}
end)
{updated_graph, scheduled_propagators}
end
defp finalize(:fail, _propagators) do
:fail
end
## At this point, the space is either solved or stable.
defp finalize(%Graph{} = residual_graph, propagators) do
(Graph.edges(residual_graph) == [] && :solved) ||
(
{g, updated_propagators} = remove_entailed_propagators(residual_graph, propagators)
{:stable, g, updated_propagators}
)
end
defp remove_entailed_propagators(graph, propagators) do
Enum.reduce(propagators, {graph, []}, fn p, {g, p_list} = _acc ->
p_vertex = ConstraintGraph.propagator_vertex(p.id)
case Graph.neighbors(g, p_vertex) do
[] -> {ConstraintGraph.remove_propagator(g, p.id), p_list}
_connected_vars -> {g, [p | p_list]}
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