Packages
fixpoint
0.17.1
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/all_different/all_different_dc.ex
defmodule CPSolver.Propagator.AllDifferent.DC do
use CPSolver.Propagator
alias CPSolver.ValueGraph
alias CPSolver.Propagator.AllDifferent.Utils, as: AllDiffUtils
alias Iter.Iterable
@moduledoc """
The domain-consistent propagator for AllDifferent constraint,
based on:
J.-C. Régin, A filtering algorithm for constraints of difference in CSPs
"""
@impl true
def arguments(args) do
Arrays.new(args, implementation: Aja.Vector)
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 filter(vars, state, changes) do
state = (state &&
state
|> Map.put(:propagator_variables, vars)
|> apply_changes(changes)) || initial_state(vars)
finalize(state)
end
defp finalize(state) do
(entailed?(state) && :passive) ||
{:state, state}
end
defp entailed?(%{sccs: sccs} = _state) do
Enum.empty?(sccs)
end
def apply_changes(
%{
sccs: sccs,
value_graph: value_graph,
propagator_variables: vars
} = state, _changes
) do
state = Map.put(state, :value_graph,
set_neighbor_finder(value_graph, ValueGraph.default_neighbor_finder(vars)))
## Apply changes to affected SCCs
Enum.reduce(sccs, Map.put(state, :sccs, MapSet.new()),
fn component, state_acc ->
%{value_graph: reduced_graph, sccs: derived_sccs} = reduce_component(component, state_acc)
state_acc
|> Map.put(:value_graph, reduced_graph)
|> Map.update!(:sccs, fn existing -> MapSet.union(existing, derived_sccs) end)
end)
end
def initial_state(vars) do
%{value_graph: value_graph, left_partition: variable_vertices, fixed_matching: _fixed_matching} =
ValueGraph.build(vars, check_matching: true)
reduce_component(variable_vertices, value_graph, vars)
|> Map.put(:propagator_variables, vars)
end
def reduce_component(component,
%{
propagator_variables: vars,
value_graph: value_graph
} = _state) do
reduce_component(component, value_graph, vars)
end
def reduce_component(component, value_graph, vars) do
reduction(vars, value_graph, component, %{})
end
def reduction(vars, value_graph, variable_vertices, fixed_matching) do
matching = find_matching(value_graph, variable_vertices, fixed_matching)
%{value_graph: _reduced_graph, sccs: _sccs} =
reduce_graph(value_graph, vars, matching)
end
def find_matching(value_graph, variable_vertices, fixed_matching) do
try do
BitGraph.Algorithm.bipartite_matching(
value_graph,
left_partition: variable_vertices,
fixed_matching: fixed_matching,
required_size: MapSet.size(variable_vertices),
process_mode: :preprocess
)
|> tap(fn matching -> matching || fail() end)
catch {:error, _} ->
fail()
end
end
def reduce_graph(value_graph, variables, %{free: free_nodes, matching: matching} = _matching_record) do
value_graph
|> build_residual_graph(variables, matching, free_nodes)
|> reduce_residual_graph(variables, matching)
|> then(fn {sccs, reduced_graph} ->
%{
sccs: sccs,
value_graph:
reduced_graph
|> remove_sink_node()
|> set_neighbor_finder(ValueGraph.default_neighbor_finder(variables))
}
end)
end
def build_residual_graph(graph, variables, matching, free_nodes) do
graph
|> add_sink_node(free_nodes)
|> then(fn g ->
set_neighbor_finder(g,
residual_graph_neighbor_finder(g, variables, matching, free_nodes)
)
end)
end
defp set_neighbor_finder(graph, neighbor_finder) do
BitGraph.set_neighbor_finder(graph, neighbor_finder)
end
defp add_sink_node(graph, free_nodes) do
Enum.empty?(free_nodes) && graph ||
BitGraph.add_vertex(graph, :sink)
end
defp remove_sink_node(graph) do
case BitGraph.V.get_vertex_index(graph, :sink) do
nil -> graph
sink_index -> BitGraph.V.delete_vertex(graph, sink_index)
end
end
defp residual_graph_neighbor_finder(value_graph, variables, matching, free_nodes) do
num_variables = ValueGraph.get_variable_count(value_graph)
base_neighbor_finder = ValueGraph.matching_neighbor_finder(value_graph, variables, matching, free_nodes)
free_node_indices = free_nodes
matching_value_indices = Map.values(matching)
sink_node_index = BitGraph.V.get_vertex_index(value_graph, :sink)
fn _graph, nil, _direction ->
## "Stray" vertex index.
## This could happen if the vertex is not in the graph,
## for instance, as a result of it being removed during graph processing;
## TODO: review
MapSet.new()
graph, vertex_index, direction ->
neighbors = base_neighbor_finder.(graph, vertex_index, direction)
## By construction of value graph, the variable vertices go first,
## followed by value vertices; the last on is 'sink' vertex
cond do
vertex_index == sink_node_index && direction == :out->
matching_value_indices
vertex_index == sink_node_index && direction == :in ->
free_node_indices
vertex_index <= num_variables ->
neighbors
direction == :in && vertex_index in free_node_indices ->
neighbors
direction == :out && vertex_index in free_node_indices ->
MapSet.new([sink_node_index])
direction == :in && vertex_index in matching_value_indices ->
Iterable.append(neighbors, sink_node_index)
direction == :out && vertex_index in matching_value_indices ->
neighbors
true ->
MapSet.new()
end
end
end
def reduce_residual_graph(residual_graph, vars, matching) do
AllDiffUtils.split_to_sccs(residual_graph, Map.keys(matching),
AllDiffUtils.default_remove_edge_fun(vars))
end
defp fail() do
throw(:fail)
end
end