Packages
fixpoint
0.18.2
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/zhang.ex
defmodule CPSolver.Propagator.AllDifferent.Zhang do
alias CPSolver.Propagator.AllDifferent.Utils, as: AllDiffUtils
import CPSolver.Utils
alias CPSolver.ValueGraph
def reduce(value_graph, free_nodes, matching, remove_edge_fun) do
value_graph
|> remove_type1_edges(free_nodes, matching, remove_edge_fun)
|> remove_type2_edges(remove_edge_fun)
end
def remove_type1_edges(graph, free_nodes, matching, process_redundant_fun) do
Enum.reduce(
free_nodes,
%{
value_graph: graph,
GA_complement_matching: matching,
process_redundant_edges: process_redundant_fun,
GA: MapSet.new(),
visited: MapSet.new(),
matching: matching,
free_nodes: free_nodes,
scheduled_for_removal: Map.new()
},
fn free_node, acc ->
if visited?(acc, free_node) do
acc
else
acc
|> Map.put(:path_GA, MapSet.new())
|> process_value_partition_node(free_node)
|> then(fn %{path_GA: delta} = processed_state ->
Map.update!(processed_state, :GA, fn ga ->
single_vertex_component?(processed_state, delta) && ga ||
MapSet.union(ga, delta) end)
end)
end
end
)
|> remove_redundant_type1_edges()
|> then(fn %{GA: ga} = state ->
Map.put(state, :components,
Enum.empty?(ga) && MapSet.new() || MapSet.new([state[:GA]]))
end)
end
def process_value_partition_node(%{value_graph: graph} = state, node) do
visited?(state, node) && state ||
(
state = mark_visited(state, node) |> unschedule_removals(node)
neighbors = BitGraph.V.in_neighbors(graph, node)
iterate(neighbors, state, fn left_partition_node, acc ->
{:cont,
(visited?(acc, left_partition_node) && acc) ||
process_variable_partition_node(acc, left_partition_node)
}
end)
)
end
def process_variable_partition_node(%{matching: matching} = state, _variable_vertex = node) do
(visited?(state, node) && state) ||
state
|> mark_visited(node)
|> Map.update!(:GA_complement_matching, fn nodes -> Map.delete(nodes, node) end)
|> Map.update!(:path_GA, fn nodes -> MapSet.put(nodes, ValueGraph.variable_index(node)) end)
|> process_value_partition_node(Map.get(matching, node))
|> schedule_removals(node)
end
### NOTE: components are sets of variable indices
### (not variable vertex indices!!!)
### TODO: consider changing for less confusion
defp single_vertex_component?(%{value_graph: graph} = state, component) do
cond do
Enum.empty?(component) -> true
MapSet.size(component) == 1 ->
vertex = MapSet.to_list(component) |> hd
Iter.Iterable.all?(BitGraph.out_neighbors(graph, vertex),
fn value_node ->
!visited?(state, value_node) &&
BitGraph.leaf_vertex?(graph, value_node)
end)
true -> false
end
end
defp schedule_removals(
%{free_nodes: free, value_graph: graph, scheduled_for_removal: scheduled} = state,
node
) do
BitGraph.V.out_neighbors(graph, node)
|> iterate(scheduled, fn right_partition_node, unvisited_acc ->
{:cont,
((visited?(state, right_partition_node) || MapSet.member?(free, right_partition_node)) &&
unvisited_acc) ||
Map.update(unvisited_acc, right_partition_node, MapSet.new([node]), fn existing ->
MapSet.put(existing, node)
end)
}
end)
|> then(fn updated_schedule -> Map.put(state, :scheduled_for_removal, updated_schedule) end)
end
## If right partition node has been visited, we unschedule all
## associated edges that were previously scheduled for removal.
defp unschedule_removals(%{scheduled_for_removal: scheduled} = state, right_partition_node) do
%{state | scheduled_for_removal: Map.delete(scheduled, right_partition_node)}
end
defp remove_redundant_type1_edges(
%{
value_graph: graph,
scheduled_for_removal: scheduled,
process_redundant_edges: process_redundant_fun
} = state
) do
updated_graph =
Enum.reduce(scheduled, graph, fn {right_partition_vertex_index, left_neighbors}, acc ->
Enum.reduce(left_neighbors, acc, fn left_vertex, acc2 ->
process_redundant_fun.(acc2, left_vertex, right_partition_vertex_index)
end)
end)
%{state | value_graph: updated_graph}
end
defp mark_visited(state, node) do
Map.update!(state, :visited, fn visited -> MapSet.put(visited, node) end)
end
defp visited?(%{visited: visited} = _state, node) do
MapSet.member?(visited, node)
end
def remove_type2_edges(%{value_graph: graph, GA_complement_matching: matching} = state, remove_edge_fun) do
(Enum.empty?(matching) && state) ||
graph
|> process_sccs(matching, remove_edge_fun)
|> then(fn {sccs, reduced_graph} ->
state
|> Map.put(:value_graph, reduced_graph)
|> Map.update!(:components, fn components -> MapSet.union(sccs, components) end)
end)
end
def process_sccs(graph, matching, remove_edge_fun) do
AllDiffUtils.split_to_sccs(graph, Map.keys(matching), remove_edge_fun)
end
end