Packages
fixpoint
0.12.5
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
@moduledoc """
The propagator for 'circuit' constraint.
"""
@impl true
def reset(args, %{domain_graph: graph} = state) do
state
|> Map.put(:domain_graph, BitGraph.update_opts(graph, neighbor_finder: neighbor_finder(args)))
|> Map.put(:propagator_variables, args)
end
def reset(_args, state) do
state
end
@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
Arrays.new(args, implementation: Aja.Vector)
end
@impl true
def filter(all_vars, nil, changes) do
filter(all_vars, initial_state(all_vars), changes)
end
def filter(all_vars, state, changes) do
updated_state = apply_changes(all_vars, state, changes)
check_state(updated_state) &&
(completed?(updated_state) && :passive
||
{:state, updated_state})
|| fail()
end
defp initial_state(args) do
l = Arrays.size(args)
domain_graph =
args
|> Enum.with_index()
|> Enum.reduce(
BitGraph.new(max_vertices: l),
fn {var, idx}, graph_acc ->
initial_reduction(var, idx, l)
BitGraph.add_vertex(graph_acc, idx)
end
)
|> BitGraph.update_opts(neighbor_finder: neighbor_finder(args))
%{
domain_graph: domain_graph,
propagator_variables: args
}
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(
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
Enum.each(BitGraph.in_neighbors(graph, successor), fn predessor ->
predessor == var_idx ||
(
res = remove(get_variable(vars, predessor), successor)
reduce_var(vars, predessor, graph, res)
)
end)
end
defp reduce_var(_vars, _var_idx, _graph, _domain_change) do
:ok
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) < Arrays.size(vars), do: fail()
## follow the chain
short_loop_check(vars, next_value, MapSet.put(fixed_chain, next_value))
end
end
end
defp check_state(%{domain_graph: graph} = _state) do
BitGraph.Algorithms.strongly_connected?(graph, algorithm: Enum.random([:tarjan, :kozaraju]))
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 ->
Stream.map(domain_values(get_variable(vars, vertex_index - 1)), fn val -> val + 1 end)
_graph, vertex_index, :in ->
for v <- vars, reduce: {1, MapSet.new()} do
{idx, n_acc} ->
{idx + 1,
contains?(v, vertex_index - 1) && MapSet.put(n_acc, idx) || n_acc}
end
|> elem(1)
end
end
end