Packages
fixpoint
0.17.5
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
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
|> branch_impl(branching, space_data)
end
defp branch_impl(variables, brancher_fun, space_data) when is_function(brancher_fun, 3) do
variables
|> filter_fixed_variables()
|> then(fn unfixed_vars ->
brancher_fun.(:branch, unfixed_vars, space_data)
|> partitions_impl(variables, space_data)
end)
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
variables
|> filter_fixed_variables()
|> brancher_impl.branch(space_data)
|> partitions_impl(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
variable_value_choice(variables, variable_choice, partition_strategy, space_data)
|> partitions_impl(variables, 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)
List.wrap(partition_record(selected_variable, domain_partitions))
end
end
defp set_domain(variable, domain) do
Map.put(variable, :domain, 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, _variables, _space_data) do
[]
end
defp partitions_impl(partitions, variables, space_data) when is_list(partitions) do
variables = Arrays.new(variables, implementation: Aja.Vector)
Enum.reduce(partitions, [], fn variable_partition, acc ->
acc ++ variable_partitions_impl(variable_partition, variables, space_data)
end)
end
## Build partitions for a single variable
defp variable_partitions_impl(%{variable_id: selected_variable_id, partitions: domain_partitions}, variables, _space_data) do
Enum.map(domain_partitions, fn {domain, constraint} ->
{Arrays.map(variables, fn var ->
domain_copy =
((var.id == selected_variable_id && domain) || var.domain)
|> Domain.copy()
set_domain(var, domain_copy)
end),
constraint}
end)
end
def partition_record(variable, domain_partitions) do
%{variable_id: variable.id, partitions: domain_partitions}
end
end