Packages
fixpoint
0.13.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
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(),
components: MapSet.new()
},
fn free_node, acc ->
if visited?(acc, free_node) do
acc
else
acc
|> Map.put(:GA, MapSet.new())
|> process_right_partition_node(free_node)
|> then(fn %{GA: ga} = type1_state ->
Map.update!(type1_state, :components,
fn components -> (MapSet.size(ga) > 1) &&
MapSet.put(components, ga) || components
end)
end)
end
end
)
|> remove_redundant_type1_edges()
end
def process_right_partition_node(%{value_graph: graph} = state, node) do
(visited?(state, node) && state) ||
(
state = mark_visited(state, node) |> unschedule_removals(node)
Enum.reduce(BitGraph.in_neighbors(graph, node), state, fn left_partition_node, acc ->
(visited?(acc, left_partition_node) && acc) ||
process_left_partition_node(acc, left_partition_node)
end)
)
end
def process_left_partition_node(%{matching: matching} = state, {:variable, variable_id} = node) do
(visited?(state, node) && state) ||
state
|> mark_visited(node)
|> Map.update!(:GA_complement_matching, fn nodes -> Map.delete(nodes, node) end)
|> Map.update!(:GA, fn nodes -> MapSet.put(nodes, variable_id) end)
|> process_right_partition_node(Map.get(matching, node))
|> schedule_removals(node)
end
defp schedule_removals(
%{free_nodes: free, value_graph: graph, scheduled_for_removal: scheduled} = state,
node
) do
BitGraph.out_neighbors(graph, node)
|> Enum.reduce(scheduled, fn right_partition_node, unvisited_acc ->
((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, left_neighbors}, acc ->
Enum.reduce(left_neighbors, acc, fn left_vertex, acc2 ->
process_redundant_fun.(acc2, left_vertex, right_partition_vertex)
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