Packages
fixpoint
0.8.51
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/variable_value/most_completed.ex
defmodule CPSolver.Search.VariableSelector.MostCompleted do
alias CPSolver.Propagator.ConstraintGraph
alias CPSolver.Search.VariableSelector.FirstFail
def candidates(_variables, space_data) do
most_completed_propagators_selection(space_data[:constraint_graph])
end
## Choose variables connected to "most completed" propagators.
## 1) Choose propagators with smallest number of still unfixed variables
## (this corresponds to propagators with smallest degree in constraint graph).
## 2) Choose variables most constrained by the propagators above.
def most_completed_propagators_selection(constraint_graph) do
## Make p => (unfixed variables) map
constraint_graph
|> Graph.edges()
|> Enum.group_by(
fn edge -> edge.v2 end,
fn edge -> edge.v1 end
)
## Pick out the propagators with minimal number of unfixed variables.
## Build the list of variable ids constrained by those propagators.
|> Enum.reduce({[], nil},
fn {_propagator_id, var_ids}, {var_ids_acc, current_min} = acc ->
var_count = length(var_ids)
cond do
is_nil(current_min) || var_count < current_min -> {var_ids, var_count}
var_count > current_min -> acc
var_count == current_min -> {var_ids ++ var_ids_acc, var_count}
end
end)
|> elem(0)
## Choose variables with the largest counts of constraints (i.e., attached propagators)
|> Enum.frequencies()
|> Enum.reduce({[], nil}, fn {var_id, var_count}, {vars_acc, current_max} = acc ->
graph_var = ConstraintGraph.get_variable(constraint_graph, var_id)
cond do
is_nil(current_max) || var_count > current_max -> {[graph_var], var_count}
var_count < current_max -> acc
var_count == current_max -> {[graph_var | vars_acc], var_count}
end
end)
|> elem(0)
end
def select_variable(variables, space_data, break_even_fun \\ &FirstFail.select_variable/1) do
## Pick out all variables with maximal degrees
candidates(variables, space_data)
|> break_even_fun.()
end
end