Packages
fixpoint
0.5.6
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(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) when is_map(propagators) do
propagators
|> Map.values()
|> reorder()
|> propagate(graph, store)
end
def propagate(propagators, graph, store) when is_list(propagators) do
propagators
|> Task.async_stream(fn 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_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
|> Map.merge(scheduled_by_propagator)
|> unschedule(p_id)
end
defp schedule_by_propagator(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, p} end
)
)}
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{} = residue, propagators) do
(Graph.vertices(residue) == [] && :solved) ||
{:stable, residue, propagators_from_graph(residue, propagators)}
end
defp propagators_from_graph(graph, propagators) do
Enum.flat_map(propagators, fn p ->
(p && ConstraintGraph.get_propagator(graph, p.id) && [p]) || []
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
Map.delete(scheduled_propagators, p_id)
end
## TODO: possible reordering strategy of propagators
## for the next pass
defp reorder(propagators) do
propagators
end
end