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/alldiff_utils.ex
defmodule CPSolver.Propagator.AllDifferent.Utils do
alias CPSolver.ValueGraph
alias CPSolver.Variable.Interface
alias BitGraph.Neighbor, as: N
## 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} = variable_vertex ->
cross_neighbors = BitGraph.V.out_neighbors(graph_acc, vertex_index)
{
MapSet.put(vertices_acc, variable_id),
remove_cross_edges(g_acc, variable_vertex, cross_neighbors, component, remove_edge_fun)
}
{: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
# defp remove_cross_edges(graph, variable_vertex, neighbors, component, remove_edge_fun) do
# case Iterable.next(neighbors) do
# :done -> graph
# {:ok, neighbor, rest} ->
# updated_graph =
# (neighbor in component) && graph ||
# remove_edge_fun.(graph, variable_vertex, BitGraph.V.get_vertex(graph, neighbor))
# remove_cross_edges(updated_graph, variable_vertex, rest, component, remove_edge_fun)
# end
# end
defp remove_cross_edges(graph, variable_vertex, neighbors, component, remove_edge_fun) do
N.iterate(neighbors, graph, fn neighbor, acc ->
if neighbor in component do
{:cont, acc}
else
{:cont, remove_edge_fun.(acc, variable_vertex, BitGraph.V.get_vertex(acc, neighbor))}
end
end)
end
def default_remove_edge_fun(vars) do
fn graph, {:variable, var_index} = var_vertex, {:value, value} = value_vertex ->
var = ValueGraph.get_variable(vars, var_index)
if Interface.fixed?(var) do
Interface.min(var) == value && graph || throw(:fail)
else
ValueGraph.delete_edge(graph, var_vertex, value_vertex, vars)
end
end
end
end