Packages
fixpoint
0.19.3
0.22.2
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/constraints/propagators/circuit.ex
defmodule CPSolver.Propagator.Circuit do
use CPSolver.Propagator
alias Iter.{Iterable.FlatMapper, Iterable.Mapper}
import CPSolver.Utils
@moduledoc """
The propagator for 'circuit' constraint.
"""
@impl true
def variables(args) do
Enum.map(args, fn x_el -> set_propagate_on(x_el, :domain_change) end)
end
@impl true
def arguments(args) do
Vector.new(args)
end
@impl true
def filter(vars, state, changes) do
if state do
update_state(state, vars)
else
initial_state(vars)
end
|> reduce_state(changes)
|> finalize()
end
def reduce_state(state, changes) do
%{domain_graph: graph} = updated_state = apply_changes(state, changes)
BitGraph.Algorithm.strongly_connected?(graph, algorithm: :tarjan) && updated_state
|| fail()
end
defp initial_state(variables) do
l = Vector.size(variables)
domain_graph =
variables
|> Enum.with_index()
|> Enum.reduce(
BitGraph.new(max_vertices: l, allocate_adjacency_table?: false),
fn {var, idx}, graph_acc ->
initial_reduction(var, idx, l)
BitGraph.add_vertex(graph_acc, idx)
end
)
%{
domain_graph: domain_graph,
}
|> update_state(variables)
end
defp update_state(state, variables) do
state
|> Map.update!(:domain_graph,
fn graph ->
BitGraph.set_neighbor_finder(graph, neighbor_finder(variables))
end)
|> Map.put(:propagator_variables, variables)
end
defp finalize(state) do
(completed?(state) && :passive
||
{:state, state})
end
defp initial_reduction(var, succ_value, circuit_length) do
## Cut the domain of variable to adhere to circuit definition.
## The values are 0-based indices.
## The successor can't point to itself.
removeBelow(var, 0)
removeAbove(var, circuit_length - 1)
remove(var, succ_value)
end
## 'vars' are successor variables in the circuit
defp apply_changes(
%{propagator_variables: vars, domain_graph: graph} = state,
changes
) do
## Side effect - the domain graph doesn't need to be updated,
## as the graph's neighbor finder for is backed by variable domains.
Enum.each(changes, fn {var_idx, domain_change} ->
reduce_var(vars, var_idx, graph, domain_change)
end)
state
end
defp reduce_var(vars, var_idx, graph, :fixed) do
successor = min(get_variable(vars, var_idx))
short_loop_check(vars, successor)
## No other variables can share the successor, so
## we will remove the successor from their domains
successor_vertex_index = successor + 1
iterate_reduction(BitGraph.V.in_neighbors(graph, successor_vertex_index), successor, graph, vars, var_idx)
end
defp reduce_var(_vars, _var_idx, _graph, _domain_change) do
:ok
end
defp iterate_reduction(neighbors, successor, graph, vars, var_idx) do
iterate(neighbors, :ok, fn predessor, _acc ->
predessor_var_index = predessor - 1
if predessor_var_index == var_idx do
{:cont, :ok}
else
res = remove(get_variable(vars, predessor_var_index), successor)
{:cont, reduce_var(vars, predessor_var_index, graph, res)}
end
end)
end
defp short_loop_check(vars, fixed_value) do
short_loop_check(vars, fixed_value, MapSet.new([fixed_value]))
end
defp short_loop_check(vars, fixed_value, fixed_chain) do
next = get_variable(vars, fixed_value)
if fixed?(next) do
next_value = min(next)
if next_value in fixed_chain do
## short loop?
if MapSet.size(fixed_chain) < Vector.size(vars), do: fail()
## follow the chain
short_loop_check(vars, next_value, MapSet.put(fixed_chain, next_value))
end
end
end
defp completed?(%{propagator_variables: variables} = _state) do
Enum.all?(variables, fn var -> fixed?(var) end)
end
defp fail() do
throw(:fail)
end
defp get_variable(vars, var_index) do
Propagator.arg_at(vars, var_index)
end
defp neighbor_finder(vars) do
fn _graph, vertex_index, :out ->
vars
|> get_variable(vertex_index - 1)
|> domain_iterator()
_graph, vertex_index, :in ->
FlatMapper.new(1..Vector.size(vars),
fn idx ->
contains?(get_variable(vars, idx - 1), vertex_index - 1) && [idx] || []
end
)
end
end
def domain_iterator(variable) do
variable
|> Interface.iterator()
|> Mapper.new(fn val -> val + 1 end)
end
def domain_set(variable) do
MapSet.new(domain_values(variable), fn val -> val + 1 end)
end
end