Packages
fixpoint
0.8.16
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/circuit.ex
defmodule CPSolver.Propagator.Circuit do
use CPSolver.Propagator
@moduledoc """
The propagator for 'circuit' constraint.
"""
@impl true
def variables(args) do
Enum.map(args, fn x_el -> set_propagate_on(x_el, :fixed) end)
end
@impl true
def filter(args) do
filter(args, initial_state(args))
end
@impl true
def filter(args, nil) do
filter(args)
end
def filter(all_vars, state) do
case update_domain_graph(all_vars, state) do
:complete ->
:passive
updated_state ->
{:state, updated_state}
end
end
defp initial_state(args) do
l = length(args)
domain_graph =
args
|> Enum.with_index()
|> Enum.reduce(Graph.new(), fn {var, idx}, graph_acc ->
initial_reduction(var, idx, l)
Enum.reduce(domain(var) |> Domain.to_list(), graph_acc, fn value, g ->
Graph.add_edge(g, idx, value)
end)
end)
%{domain_graph: domain_graph, unfixed_vertices: Graph.vertices(domain_graph)}
end
defp initial_reduction(var, succ_value, circuit_length) do
## Cut the domain of variable to adhere to circuit definition.
## The values are 0-based indices.
## The successor can't point to itself.
removeBelow(var, 0)
removeAbove(var, circuit_length - 1)
remove(var, succ_value)
end
## 'vars' are successor variables in the circuit
defp update_domain_graph(
vars,
%{domain_graph: %Graph{} = graph, unfixed_vertices: unfixed_vertices} = _current_state
) do
case reduce_graph(graph, vars, unfixed_vertices) do
:fail ->
fail()
{updated_graph, updated_unfixed_vertices} ->
(MapSet.size(updated_unfixed_vertices) == 0 && :complete) ||
%{domain_graph: updated_graph, unfixed_vertices: updated_unfixed_vertices}
end
end
defp reduce_graph(graph, vars, unfixed_vertices) when is_map(unfixed_vertices) do
reduce_graph(graph, vars, MapSet.to_list(unfixed_vertices))
end
defp reduce_graph(graph, vars, unfixed_vertices) when is_list(unfixed_vertices) do
reduce_graph(graph, vars, unfixed_vertices, MapSet.new())
end
##
@spec reduce_graph(
graph :: Graph.t(),
vars :: [Variable.t()],
unfixed_vertices :: [integer()],
remaining_unfixed_vertices :: MapSet.t()
) ::
{Graph.t(), [integer]}
## All unfixed vertices have been processed
defp reduce_graph(%Graph{} = graph, _vars, [], remaining_unfixed_vertices) do
(check_graph(graph, remaining_unfixed_vertices) &&
{graph, remaining_unfixed_vertices}) || fail()
end
defp reduce_graph(
%Graph{} = graph,
vars,
[idx | rest] = _unfixed_vertices,
ids_to_revisit
) do
## Check if the (unfixed) vertex has already been scheduled for the next stage
if MapSet.member?(ids_to_revisit, idx) do
reduce_graph(graph, vars, rest, ids_to_revisit)
else
var = Enum.at(vars, idx)
if fixed?(var) do
successor_vertex = min(var)
{reduced_graph, reduced_unfixed_vertices} =
reduce_with_fixed(graph, vars, idx, successor_vertex, ids_to_revisit)
reduce_graph(
reduced_graph,
vars,
rest,
MapSet.difference(ids_to_revisit, reduced_unfixed_vertices)
)
else
reduce_graph(graph, vars, rest, MapSet.put(ids_to_revisit, idx))
end
end
end
defp reduce_with_fixed(graph, vars, idx, successor, unfixed_vertices) do
graph
|> remove_out_edges(idx, successor)
|> remove_in_edges(successor, idx, vars, unfixed_vertices)
end
## Remove all out-edges for vertex_id except (vertex_id, successor_id) one
defp remove_out_edges(%Graph{} = graph, vertex_id, successor_id) do
Enum.reduce(Graph.out_edges(graph, vertex_id), graph, fn
%{v2: neighbour_id} = _out_edge, g_acc when neighbour_id == successor_id -> g_acc
%{v2: neighbour_id} = _out_edge, g_acc -> delete_edge(g_acc, vertex_id, neighbour_id)
end)
end
## Remove all in-edges for successor_id except (vertex_id, successor_id)
def remove_in_edges(%Graph{} = graph, successor_id, vertex_id, vars, unfixed_vertices) do
Enum.reduce(Graph.in_edges(graph, successor_id), {graph, unfixed_vertices}, fn
%{v1: neighbour_id} = _in_edge, acc when neighbour_id == vertex_id ->
acc
%{v1: neighbour_id} = _in_edge, {g_acc, unfixed_acc} ->
var = Enum.at(vars, neighbour_id)
{delete_edge(g_acc, neighbour_id, successor_id),
(:fixed == remove(var, successor_id) && MapSet.delete(unfixed_acc, successor_id)) ||
unfixed_acc}
end)
end
defp check_graph(%Graph{} = graph, _fixed_vertices) do
length(Graph.strong_components(graph)) == 1
end
defp delete_edge(%Graph{} = graph, vertex1, vertex2) do
Graph.delete_edge(graph, vertex1, vertex2)
|> tap(fn g ->
(Graph.in_neighbors(g, vertex2) == [] ||
Graph.out_neighbors(g, vertex1) == []) &&
fail()
end)
end
defp fail() do
throw(:fail)
end
end