Packages
fixpoint
0.8.49
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/strategy.ex
defmodule CPSolver.Search.Strategy do
alias CPSolver.Variable.Interface
alias CPSolver.Search.VariableSelector.{FirstFail, MostConstrained}
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search.ValueSelector.{Min, Max, Random}
require Logger
def default_strategy() do
{
:first_fail,
:indomain_min
}
end
def shortcut(:first_fail) do
&FirstFail.select_variable/1
end
def shortcut(:input_order) do
fn variables ->
Enum.sort_by(variables, fn %{index: idx} -> idx end)
|> List.first()
end
end
def shortcut(:most_constrained) do
&MostConstrained.select_variable/2
end
def shortcut(:indomain_min) do
Min
end
def shortcut(:indomain_max) do
Max
end
def shortcut(:indomain_random) do
Random
end
def most_constrained(break_even_fun \\ first_fail())
def most_constrained(break_even_fun) when is_function(break_even_fun) do
fn vars, data -> MostConstrained.select_variable(vars, data, break_even_fun) end
end
def most_constrained(shortcut) when is_atom(shortcut) do
most_constrained(shortcut(shortcut))
end
def first_fail(break_even_fun \\ &List.first/1)
def first_fail(break_even_fun) when is_function(break_even_fun, 1) do
first_fail(fn vars, _data -> break_even_fun.(vars) end)
end
def first_fail(break_even_fun) when is_function(break_even_fun, 2) do
fn vars, data ->
vars
|> FirstFail.get_minimals()
|> break_even_fun.(data)
end
end
def first_fail(shortcut) when is_atom(shortcut) do
first_fail(shortcut(shortcut))
end
def select_variable(variables, variable_choice) when is_atom(variable_choice) do
select_variable(variables, shortcut(variable_choice))
end
def select_variable(variables, variable_choice) when is_function(variable_choice) do
variables
|> Enum.reject(fn v -> Interface.fixed?(v) end)
|> then(fn
[] -> throw(all_vars_fixed_exception())
unfixed_vars -> variable_choice.(unfixed_vars)
end)
end
defp partition_impl(variable, value_choice) when is_atom(value_choice) do
shortcut(value_choice).select_value(variable)
end
defp partition_impl(variable, value_choice) when is_function(value_choice) do
value_choice.(variable)
end
def branch(variables, {variable_choice, partition_strategy}) do
branch(variables, variable_choice, partition_strategy, %{})
end
def branch(variables, {variable_choice, partition_strategy}, data) do
branch(variables, variable_choice, partition_strategy, data)
end
def branch(variables, variable_choice, partition_strategy, data \\ %{})
def branch(variables, variable_choice, partition_strategy, data) when is_atom(variable_choice) do
branch(variables, shortcut(variable_choice), partition_strategy, data)
end
def branch(variables, variable_choice, partition_strategy, data) when is_function(variable_choice, 2) do
variable_choice_arity1 = fn variables -> variable_choice.(variables, data) end
branch(variables, variable_choice_arity1, partition_strategy, data)
end
def branch(variables, variable_choice, partition_strategy, _data) when is_function(variable_choice, 1)
do
case select_variable(variables, variable_choice) do
nil ->
[]
selected_variable ->
{:ok, domain_partitions} =
partition(selected_variable, partition_strategy)
variable_partitions(selected_variable, domain_partitions, variables)
end
end
def partition(variable, value_choice) do
variable
|> partition_impl(value_choice)
|> split_domain_by(variable)
end
def all_vars_fixed_exception() do
:all_vars_fixed
end
def failed_variables_in_search_exception() do
:failed_variables_in_search
end
defp set_domain(variable, domain) do
Map.put(variable, :domain, domain)
end
defp variable_partitions(selected_variable, domain_partitions, variables) do
Enum.map(domain_partitions, fn {domain, constraint} ->
{Enum.map(variables, fn var ->
domain_copy =
((var.id == selected_variable.id && domain) || var.domain)
# var.domain
|> Domain.copy()
set_domain(var, domain_copy)
end), constraint}
end)
end
defp split_domain_by(value, variable) do
domain = Interface.domain(variable)
try do
{remove_changes, _domain} = Domain.remove(domain, value)
{:ok,
[
{
Domain.new(value),
%{variable.id => :fixed}
# Equal.new(variable, value)
},
{
domain,
%{variable.id => remove_changes}
# NotEqual.new(variable, value)
}
]}
rescue
:fail ->
Logger.error(
"Failure on partitioning with value #{inspect(value)}, domain: #{inspect(CPSolver.BitVectorDomain.raw(domain))}"
)
throw(:fail)
end
end
end