Packages
fixpoint
0.12.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
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
BitGraph.Algorithms.strong_components(graph,
vertices: Map.keys(matching),
component_handler:
{fn component, acc -> scc_component_handler(component, remove_edge_fun, acc) end,
{MapSet.new(), graph}},
algorithm: :tarjan
)
end
def scc_component_handler(component, remove_edge_fun, {component_acc, graph_acc} = _current_acc) do
{variable_vertices, updated_graph} =
Enum.reduce(component, {MapSet.new(), graph_acc}, fn vertex_index,
{vertices_acc, g_acc} = acc ->
case BitGraph.V.get_vertex(graph_acc, vertex_index) do
## We only need to remove out-edges from 'variable' vertices
## that cross to other SCCS
{:variable, variable_id} = v ->
foreign_neighbors = BitGraph.E.out_neighbors(g_acc, vertex_index)
{
MapSet.put(vertices_acc, variable_id),
Enum.reduce(foreign_neighbors, g_acc, fn neighbor, g_acc2
when is_integer(neighbor) ->
(neighbor in component && g_acc2) ||
remove_edge_fun.(g_acc2, v, BitGraph.V.get_vertex(g_acc2, neighbor))
end)
}
{:value, _} ->
acc
end
end)
## drop 1-vertex sccs
updated_components =
MapSet.size(variable_vertices) > 1 && MapSet.put(component_acc, variable_vertices) || component_acc
{updated_components, updated_graph}
end
end