Packages
fixpoint
0.21.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/search/search.ex
defmodule CPSolver.Search do
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search.VariableSelector
alias CPSolver.Search.Partition
alias CPSolver.Utils.Vector
alias CPSolver.Variable.UnfixedTracker, as: Tracker
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, 2) do
brancher_fun.(:init, space_data)
end
def branch(branching, space_data) do
if Tracker.empty?(space_data[:unfixed_variables_tracker]) do
throw(:all_vars_fixed)
else
case branch_impl(branching, space_data) do
nil ->
branch_impl(default_strategy(), space_data)
branching ->
branching
end
|> partitions_impl()
end
end
defp branch_impl(brancher_fun, space_data) when is_function(brancher_fun, 2) do
brancher_fun.(:branch, space_data)
end
defp branch_impl(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
space_data
|> brancher_impl.branch(space_data)
else
throw({:unknown_brancher, brancher_impl})
end
end
defp branch_impl({variable_choice, partition_strategy}, space_data) do
branch_impl(variable_choice, partition_strategy, space_data)
end
defp branch_impl(variable_choice, partition_strategy, space_data) do
branch_impl(
fn :branch, space_data ->
variable_value_choice(variable_choice, partition_strategy, space_data)
end,
space_data
)
end
def variable_value_choice(variable_choice, partition_strategy, space_data) do
case VariableSelector.select_variable(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 partitions_impl(nil) do
[]
end
defp partitions_impl(partitions) when is_list(partitions) do
Enum.reduce(partitions, [], fn variable_partition, acc ->
acc ++ variable_partitions_impl(variable_partition)
end)
end
## Build partitions for a single variable
defp variable_partitions_impl(domain_partitions) 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: variables} = space_data ->
{_idx, variable_copies, domain_changes} =
Vector.reduce(variables, {0, variables, Map.new()}, fn var,
{var_idx, 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
{
var_idx + 1,
Vector.update(variables_acc, var_idx, var_copy),
changes_acc
}
end)
## Create a copy of "unfixed variables" tracker.
##
tracker_copy =
case space_data[:unfixed_variables_tracker] do
nil -> nil
tracker -> Tracker.copy(tracker)
end
%{
variable_copies: variable_copies,
domain_changes: domain_changes,
unfixed_variables_tracker: tracker_copy
}
end
end
end