Packages
fixpoint
0.11.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
@moduledoc """
The propagator for 'circuit' constraint.
"""
@impl true
def reset(_args, %{domain_graph: graph} = state) do
Map.put(state, :domain_graph, BitGraph.copy(graph))
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)
max_vertices = Enum.reduce(args, l, fn var, acc -> acc + size(var) end)
domain_graph =
args
|> Enum.with_index()
|> Enum.reduce(
BitGraph.new(max_vertices: max_vertices),
fn {var, idx}, graph_acc ->
initial_reduction(var, idx, l)
Enum.reduce(domain_values(var), graph_acc, fn value, g ->
BitGraph.add_edge(g, idx, value)
end)
end
)
%{
domain_graph: domain_graph
}
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
Map.put(state, :domain_graph,
Enum.reduce(changes, graph, fn {var_idx, domain_change}, graph_acc ->
reduce_var(vars, var_idx, graph_acc, domain_change)
end)
)
end
defp reduce_var(vars, var_idx, graph, :fixed) do
successor = min(Propagator.arg_at(vars, var_idx))
## No other variables can share the successor, so
## we will remove the successor from their domains
Enum.reduce(BitGraph.in_neighbors(graph, successor), graph, fn predessor, graph_acc ->
predessor == var_idx && graph_acc ||
(
res = remove(Propagator.arg_at(vars, predessor), successor)
g = BitGraph.delete_edge(graph_acc, predessor, successor)
reduce_var(vars, predessor, g, res)
)
end)
end
defp reduce_var(vars, var_idx, graph, _domain_change) do
new_successors = domain_values(Propagator.arg_at(vars, var_idx))
current_successors = BitGraph.out_neighbors(graph, var_idx)
## `new_successors` is always a subset of `current_successors`
## We remove edges that are a difference between these two sets
Enum.reduce(MapSet.difference(current_successors, new_successors),
graph, fn s, graph_acc ->
BitGraph.delete_edge(graph_acc, var_idx, s)
end)
end
defp check_state(%{domain_graph: graph} = _state) do
try do
BitGraph.Algorithms.strong_components(graph,
algorithm: :tarjan,
component_handler: fn component, _dfs_state ->
throw({:single_scc?, component && (MapSet.size(component) == BitGraph.num_vertices(graph))})
end)
catch
{:single_scc?, res} -> res
end
end
defp completed?(%{domain_graph: graph} = _state) do
BitGraph.num_vertices(graph) == BitGraph.num_edges(graph)
end
defp fail() do
throw(:fail)
end
end