Packages
fixpoint
0.7.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/space.ex
defmodule CPSolver.Space do
@moduledoc """
Computation space.
The concept is taken from Chapter 12, "Concepts, Techniques, and Models
of Computer Programming" by Peter Van Roy and Seif Haridi.
"""
alias CPSolver.Utils
alias CPSolver.ConstraintStore
alias CPSolver.Search.Strategy, as: Search
alias CPSolver.Solution, as: Solution
alias CPSolver.Propagator.ConstraintGraph
alias CPSolver.Utils
alias CPSolver.Space.Propagation
alias CPSolver.Objective
alias CPSolver.Shared
require Logger
@behaviour GenServer
def default_space_opts() do
[
store_impl: CPSolver.ConstraintStore.default_store(),
solution_handler: Solution.default_handler(),
search: Search.default_strategy(),
max_space_threads: 8,
postpone: false
]
end
def create(variables, propagators, space_opts \\ default_space_opts()) do
propagators = maybe_add_objective_propagator(propagators, space_opts[:objective])
{:ok, _space} =
create(%{
variables: variables,
propagators: propagators,
constraint_graph: ConstraintGraph.create(propagators),
opts: space_opts
})
end
defp maybe_add_objective_propagator(propagators, nil) do
propagators
end
defp maybe_add_objective_propagator(propagators, objective) do
[objective.propagator | propagators]
end
def create(data) do
if CPSolver.complete?(data.opts[:solver_data]) do
{:error, :complete}
else
GenServer.start(__MODULE__, data)
end
end
def start_propagation(space_pid) when is_pid(space_pid) do
try do
:done = GenServer.call(space_pid, :propagate, :infinity)
catch
:exit, {:normal, {GenServer, :call, _}} = _reason ->
:ignore
end
end
def start_propagation(space_pid, shared) do
if Shared.checkout_space_thread(shared) do
spawn(fn ->
start_propagation(space_pid)
Shared.checkin_space_thread(shared)
end)
else
start_propagation(space_pid)
end
end
@impl true
def init(%{variables: variables, opts: space_opts, constraint_graph: graph} = data) do
{:ok, space_variables, store} =
ConstraintStore.create_store(variables,
store_impl: space_opts[:store_impl],
space: self()
)
space_data =
data
|> maybe_bind_objective_variable(store)
|> Map.put(:id, make_ref())
|> Map.put(:variables, space_variables)
|> Map.put(:store, store)
|> Map.put(:constraint_graph, ConstraintGraph.remove_fixed(graph, space_variables))
Shared.add_active_spaces(data.opts[:solver_data], [self()])
(space_opts[:postpone] &&
{:ok, space_data}) || {:ok, space_data, {:continue, :propagate}}
end
defp maybe_bind_objective_variable(data, store) do
case data.opts[:objective] do
nil ->
data
objective ->
put_in(data, [:opts, :objective], Objective.bind_to_store(objective, store))
end
end
@impl true
def handle_continue(:propagate, data) do
(data.opts[:postpone] && {:noreply, data}) ||
data
|> propagate()
|> tap(fn _ ->
caller = Map.get(data, :caller)
caller && GenServer.reply(caller, :done)
end)
end
@impl true
def handle_call(:propagate, caller, data) do
propagate(Map.put(data, :caller, caller))
end
defp propagate(
%{
propagators: propagators,
variables: variables,
constraint_graph: constraint_graph,
store: store
} =
data
) do
case Propagation.run(propagators, constraint_graph, store) do
:fail ->
handle_failure(data)
:solved ->
handle_solved(data)
{:stable, reduced_constraint_graph, reduced_propagators} ->
%{
data
| constraint_graph: reduced_constraint_graph,
propagators: reduced_propagators,
variables: variables
}
|> handle_stable()
end
end
defp handle_failure(data) do
shutdown(data, :failure)
end
defp handle_solved(data) do
data
|> solution()
|> then(fn
:fail ->
shutdown(data, :fail)
solution ->
maybe_tighten_objective_bound(data.opts[:objective])
Solution.run_handler(solution, data.opts[:solution_handler])
shutdown(data, :solved)
end)
end
defp solution(%{variables: variables, store: store} = _data) do
Enum.reduce_while(variables, Map.new(), fn var, acc ->
case ConstraintStore.get(store, var, :min) do
:fail -> {:halt, :fail}
val -> {:cont, Map.put(acc, var.name, val)}
end
end)
end
defp maybe_tighten_objective_bound(nil) do
:ok
end
defp maybe_tighten_objective_bound(objective) do
Objective.tighten(objective)
end
defp handle_stable(%{variables: variables} = data) do
{localized_vars, _all_fixed?} = Utils.localize_variables(variables)
distribute(%{data | variables: localized_vars})
end
def distribute(
%{
opts: opts,
variables: localized_variables
} = data
) do
## The search strategy branches off the existing variables.
## Each branch is a list of variables to use by a child space
branches = Search.branch(localized_variables, opts[:search])
Enum.take_while(branches, fn variable_copies ->
case create(
data
|> Map.put(:variables, variable_copies)
|> Map.put(:opts, Keyword.put(data.opts, :postpone, true))
) do
{:ok, space_pid} ->
start_propagation(space_pid, data.opts[:solver_data])
{:error, :complete} ->
false
end
end)
shutdown(data, :distribute)
end
defp shutdown(data, reason) do
{:stop, :normal, (!data[:finalized] && cleanup(data, reason)) || data}
end
defp cleanup(data, reason) do
Shared.remove_space(data.opts[:solver_data], self(), reason)
caller = data[:caller]
caller && GenServer.reply(caller, :done)
Map.put(data, :finalized, true)
end
@impl true
def terminate(reason, data) do
shutdown(data, reason)
end
end