Packages
fixpoint
0.8.44
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
alias CPSolver.DefaultDomain, as: Domain
# alias CPSolver.Constraint.{Equal, NotEqual}
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(:indomain_min) do
Min
end
def shortcut(:indomain_max) do
Max
end
def shortcut(:indomain_random) do
Random
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) 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