Packages
fixpoint
0.8.21
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)
{circuit, unfixed_vertices, domain_graph} =
args
|> Enum.with_index()
|> Enum.reduce(
{List.duplicate(nil, l), [], Graph.new()},
fn {var, idx}, {circuit_acc, unfixed_acc, graph_acc} ->
initial_reduction(var, idx, l)
fixed? = fixed?(var)
circuit_acc =
(fixed? && update_circuit(circuit_acc, idx, min(var))) ||
circuit_acc
unfixed_acc = (fixed? && unfixed_acc) || [idx | unfixed_acc]
{circuit_acc, unfixed_acc,
Enum.reduce(domain(var) |> Domain.to_list(), graph_acc, fn value, g ->
Graph.add_edge(g, idx, value)
end)}
end
)
%{
domain_graph: domain_graph,
circuit: Enum.reverse(circuit),
unfixed_vertices: unfixed_vertices
}
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, circuit: circuit, unfixed_vertices: unfixed_vertices} = _state
) do
case reduce_graph(vars, graph, circuit, unfixed_vertices) do
:fail ->
fail()
state ->
(Enum.empty?(state.unfixed_vertices) &&
:complete) ||
state
end
end
defp reduce_graph(vars, graph, circuit, unfixed_vertices) do
reduce_graph(vars, graph, circuit, unfixed_vertices, [])
end
defp reduce_graph(vars, graph, circuit, [vertex | rest], remaining_unfixed) do
var = Enum.at(vars, vertex)
if fixed?(var) do
succ = min(var)
{updated_graph, in_neighbours} = fix_vertex(graph, vertex, succ)
## As the successor is assigned to vertex, no other neighbours of successor can have it in their domains
Enum.each(in_neighbours, fn in_n_vertex -> remove(Enum.at(vars, in_n_vertex), succ) end)
reduce_graph(
vars,
updated_graph,
update_circuit(circuit, vertex, succ),
rest,
remaining_unfixed
)
else
reduce_graph(vars, graph, circuit, rest, [vertex | remaining_unfixed])
end
end
defp reduce_graph(_vars, graph, circuit, [], unfixed_vertices_map) do
(check_graph(graph, circuit) &&
%{
domain_graph: graph,
circuit: circuit,
unfixed_vertices: unfixed_vertices_map
}) ||
fail()
end
defp fix_vertex(graph, vertex, value) do
graph
|> remove_out_edges(vertex, value)
|> remove_in_edges(value, vertex)
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) do
Enum.reduce(Graph.in_edges(graph, successor_id), {graph, []}, fn
%{v1: neighbour_id} = _in_edge, acc when neighbour_id == vertex_id ->
acc
%{v1: neighbour_id} = _in_edge, {g_acc, in_neighbours_acc} ->
{delete_edge(g_acc, neighbour_id, successor_id), [neighbour_id | in_neighbours_acc]}
end)
end
def check_circuit(_partial_circuit, nil) do
true
end
def check_circuit(partial_circuit, start_at) do
check_circuit(partial_circuit, start_at, Enum.at(partial_circuit, start_at), 1)
end
defp check_circuit(_partial_circuit, _started_at, nil, _step) do
true
end
defp check_circuit(partial_circuit, started_at, currently_at, step)
when started_at == currently_at do
step == length(partial_circuit)
end
defp check_circuit(partial_circuit, started_at, currently_at, step) do
check_circuit(partial_circuit, started_at, Enum.at(partial_circuit, currently_at), step + 1)
end
defp check_graph(%Graph{} = graph, _fixed_vertices) do
length(Graph.strong_components(graph)) == 1
end
defp update_circuit(circuit, idx, value) do
List.replace_at(circuit, idx, value)
|> tap(fn partial_circuit -> check_circuit(partial_circuit, idx) || fail() end)
end
defp delete_edge(%Graph{} = graph, vertex1, vertex2) do
Graph.delete_edge(graph, vertex1, vertex2)
|> tap(fn g ->
Graph.out_neighbors(g, vertex1) == [] &&
fail()
end)
end
defp fail() do
throw(:fail)
end
end