Packages
fixpoint
0.20.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/search/search.ex
defmodule CPSolver.Search do
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search.VariableSelector
alias CPSolver.Search.Partition
alias CPSolver.Variable.Interface
alias CPSolver.Utils.Vector
require Logger
def default_strategy() do
CPSolver.Search.DefaultBrancher
end
def initialize({variable_choice, value_choice} = _search, space_data) do
{
VariableSelector.initialize(variable_choice, space_data),
Partition.initialize(value_choice, space_data)
}
end
def initialize(brancher_impl, data) when is_atom(brancher_impl) do
if Code.ensure_loaded(brancher_impl) == {:module, brancher_impl} &&
function_exported?(brancher_impl, :branch, 2) do
brancher_impl.initialize(data)
else
throw({:unknown_brancher, brancher_impl})
end
end
def initialize(brancher_fun, space_data) when is_function(brancher_fun, 3) do
brancher_fun.(:init, space_data, nil)
end
### Helpers
def branch(variables, branching, space_data \\ %{})
def branch(variables, branching, space_data) do
variables
|> filter_fixed_variables()
|> then(fn unfixed_vars ->
unfixed_vars
|> branch_impl(branching, space_data)
|> then(fn branching -> branching || branch_impl(variables, default_strategy(), space_data) end)
|> partitions_impl(space_data)
end)
end
defp branch_impl(variables, brancher_fun, space_data) when is_function(brancher_fun, 3) do
brancher_fun.(:branch, variables, space_data)
end
defp branch_impl(variables, brancher_impl, space_data) when is_atom(brancher_impl) do
if Code.ensure_loaded(brancher_impl) == {:module, brancher_impl} &&
function_exported?(brancher_impl, :branch, 2) do
brancher_impl.branch(variables, space_data)
else
throw({:unknown_brancher, brancher_impl})
end
end
defp branch_impl(variables, {variable_choice, partition_strategy}, space_data) do
branch_impl(variables, variable_choice, partition_strategy, space_data)
end
defp branch_impl(variables, variable_choice, partition_strategy, space_data) do
branch_impl(
variables,
fn :branch, variables, space_data ->
variable_value_choice(variables, variable_choice, partition_strategy, space_data)
end,
space_data
)
end
def variable_value_choice(variables, variable_choice, partition_strategy, space_data) do
case VariableSelector.select_variable(variables, space_data, variable_choice) do
nil ->
[]
selected_variable ->
{:ok, domain_partitions} =
Partition.partition(selected_variable, partition_strategy)
domain_partitions
end
end
defp copy_variable(%{domain: domain} = variable) do
Map.put(variable, :domain, Domain.copy(domain))
end
defp filter_fixed_variables(vars) do
case Enum.reject(vars, fn var -> Interface.fixed?(var) end) do
[] ->
throw(:all_vars_fixed)
unfixed_vars ->
unfixed_vars
end
end
defp partitions_impl(nil, _space_data) do
[]
end
defp partitions_impl(partitions, space_data) when is_list(partitions) do
Enum.reduce(partitions, [], fn variable_partition, acc ->
acc ++ variable_partitions_impl(variable_partition, space_data)
end)
end
## Build partitions for a single variable
defp variable_partitions_impl(domain_partitions, _space_data) do
Enum.map(List.wrap(domain_partitions), fn partition ->
build_reduction(partition)
end)
end
## Partition is a map %{var_id => reduction}
## `reduction is a function that takes a variable
## and performs domain reduction.
##
defp build_reduction(partition) do
fn variables ->
var_array = Vector.new([])
Enum.reduce(variables, {var_array, Map.new()}, fn var, {variables_acc, changes_acc} ->
var_copy = copy_variable(var)
changes_acc =
case Map.get(partition, var.id) do
nil -> changes_acc
reduction -> Map.put(changes_acc, var.id, reduction.(var_copy))
end
{
Vector.append(variables_acc, var_copy),
changes_acc
}
end)
end
end
end