Packages
fixpoint
0.5.3
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(propagators, constraint_graph, _store) when map_size(propagators) == 0 do
constraint_graph
end
defp run_impl(propagators, constraint_graph, store) do
case propagate(propagators, store) do
:fail ->
:fail
changes when map_size(changes) == 0 ->
constraint_graph
changes ->
{reduced_graph, active_propagators} = wakeup(changes, constraint_graph)
run_impl(active_propagators, reduced_graph, store)
end
end
defp propagate(map, _store) when map_size(map) == 0 do
:no_changes
end
@spec propagate(map(), map()) :: :fail | :no_changes | {:changes, map()}
defp propagate(propagators, store) do
propagators
|> Task.async_stream(fn {_ref, p} -> Propagator.filter(p, store: store) end)
|> Enum.reduce_while(%{}, fn {:ok, res}, acc ->
case res do
{:changed, changes} ->
{:cont,
Map.merge(acc, changes, fn _var, prev_event, new_event ->
merge_events(prev_event, new_event)
end)}
:stable ->
{:cont, acc}
{:fail, _var} ->
{:halt, :fail}
end
end)
end
defp finalize(:fail, _propagators) do
:fail
end
## At this point, the space is either solved or stable.
## Reduce constraint graph and interpret the result.
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
## Wake up propagators based on the changes
defp wakeup(changes, graph) when is_map(changes) do
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)
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 merge_events(prev_event, new_event) when prev_event == :fixed or new_event == :fixed do
:fixed
end
## TODO! Use hierarchy (i.e. fixed -> (min__change or max_change) -> bound_change -> domain_change)
defp merge_events(_prev_event, new_event) do
new_event
end
end