Packages
fixpoint
0.5.0
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.Propagator
alias CPSolver.Solution, as: Solution
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Propagator.ConstraintGraph
alias CPSolver.Utils
alias CPSolver.Space.Propagation
alias CPSolver.Shared
require Logger
@behaviour GenServer
def default_space_opts() do
[
store_impl: CPSolver.ConstraintStore.default_store(),
solution_handler: Solution.default_handler(),
search: CPSolver.Search.Strategy.default_strategy(),
solver_data: Shared.init_shared_data(),
keep_alive: false
]
end
def create(variables, propagators, space_opts \\ default_space_opts()) do
{:ok, _space} =
create(%{
variables: variables,
propagators: Map.new(propagators, fn p -> {make_ref(), Propagator.normalize(p)} end),
opts: space_opts
})
end
def create(data) do
if CPSolver.complete?(data.opts[:solver_data]) do
{:error, :complete}
else
GenServer.start(__MODULE__, data)
end
end
@impl true
def init(%{variables: variables, propagators: propagators, opts: space_opts} = _data) do
space_id = make_ref()
{:ok, space_variables, store} =
ConstraintStore.create_store(variables,
store_impl: space_opts[:store_impl],
space: self()
)
space_propagators =
bind_propagators(propagators, store)
space_data = %{
id: space_id,
variables: space_variables,
propagators: space_propagators,
constraint_graph: ConstraintGraph.create(space_propagators),
store: store,
opts: space_opts
}
{:ok, space_data, {:continue, :propagate}}
end
defp bind_propagators(propagators, store) do
Map.new(
propagators,
fn {ref, {mod, args}} ->
{ref,
{mod,
Enum.map(args, fn
%CPSolver.Variable{} = arg -> Map.put(arg, :store, store)
const -> const
end)}}
end
)
end
@impl true
def handle_continue(:propagate, data) do
propagate(data)
end
defp propagate(
%{propagators: propagators, variables: variables, constraint_graph: constraint_graph} =
data
) do
Shared.add_active_spaces(data.opts[:solver_data], [self()])
case Propagation.run(propagators, variables, constraint_graph) 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 ->
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 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
case branching(localized_variables, opts[:search]) do
{:ok, {var_to_branch_on, domain_partitions}} ->
Enum.map(domain_partitions, fn partition ->
variable_copies =
Enum.map(localized_variables, fn %{id: clone_id} = clone ->
if clone_id == var_to_branch_on.id do
Map.put(clone, :domain, Domain.new(partition))
else
clone
end
end)
create(
data
|> Map.put(:variables, variable_copies)
)
end)
shutdown(data, :distribute)
end
end
defp branching(variables, search_strategy) do
case search_strategy.select_variable(variables) do
{:ok, var_to_branch_on} ->
var_domain = var_to_branch_on.domain
case search_strategy.partition(var_domain) do
:fail -> :fail
{:ok, partitions} -> {:ok, {var_to_branch_on, partitions}}
end
error ->
error
end
end
defp shutdown(data, reason) do
Shared.remove_space(data.opts[:solver_data], self(), reason)
{:stop, :normal, data}
end
def get_state_and_data(space) do
{_state, _data} = :sys.get_state(space)
end
end