Packages
fixpoint
0.12.4
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/utils.ex
defmodule CPSolver.Propagator.AllDifferent.Utils do
alias CPSolver.ValueGraph
alias CPSolver.Variable.Interface
## Splits graph into SCCs,
## and removes cross-edges.
## `vertices` is a subset of graph vertices
## that DFS will be run on.
## This means the split will be made on parts of the graph that
## are reachable from these vertices.
## `remove_edge_fun/3` is a function
## fn(graph, from_vertex, to_vertex)
## that returns (possibly modified) graph.
##
## Returns tuple {sccs, reduced_graph}
def split_to_sccs(graph, vertices, remove_edge_fun \\ fn graph, from, to -> BitGraph.delete_edge(graph, from, to) end) do
BitGraph.Algorithms.strong_components(graph,
vertices: vertices,
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
_ ->
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
def default_remove_edge_fun(vars) do
fn graph, {:variable, var_index} = var_vertex, value_vertex ->
var = ValueGraph.get_variable(vars, var_index)
if Interface.fixed?(var) do
graph
else
ValueGraph.delete_edge(graph, var_vertex, get_value_vertex(value_vertex), vars)
end
end
end
## Helpers
defp get_value_vertex({:value, _vertex} = v) do
v
end
defp get_value_vertex(vertex) when is_integer(vertex) do
{:value, vertex}
end
end