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/core/propagator/constraint_graph.ex
defmodule CPSolver.Propagator.ConstraintGraph do
@moduledoc """
The constraint graph connects propagators and their variables.
The edge between a propagator and a variable represents a notification
the propagator receives upon varable's domain change.
"""
alias CPSolver.Propagator
alias CPSolver.Variable.Interface
alias CPSolver.DefaultDomain, as: Domain
@spec create([Propagator.t()] | %{reference() => Propagator.t()}) :: Graph.t()
def create(propagators) when is_list(propagators) do
propagators
|> Enum.map(fn p -> {p.id, p} end)
|> Map.new()
|> create()
end
def create(propagators) when is_map(propagators) do
Enum.reduce(propagators, Graph.new(), fn {propagator_id,
%{mod: propagator_mod, args: args} = p},
acc ->
args
|> propagator_mod.variables()
|> Enum.reduce(acc, fn var, acc2 ->
Graph.add_vertex(acc2, propagator_vertex(propagator_id))
|> Graph.add_edge({:variable, Interface.id(var)}, propagator_vertex(propagator_id),
label: get_propagate_on(var)
)
end)
|> Graph.label_vertex(propagator_vertex(propagator_id), p)
end)
end
def get_propagator_ids(constraint_graph, variable_id, filter_fun)
when is_function(filter_fun) do
constraint_graph
|> Graph.edges({:variable, variable_id})
|> Enum.flat_map(fn edge ->
if filter_fun.(edge) do
{:propagator, p_id} = edge.v2
[p_id]
else
[]
end
end)
end
## Get a list of propagator ids that "listen" to the domain change of given variable.
def get_propagator_ids(
constraint_graph,
variable_id,
domain_change
) do
get_propagator_ids(constraint_graph, variable_id, fn edge -> domain_change in edge.label end)
end
def has_variable?(graph, variable_id) do
Graph.has_vertex?(graph, {:variable, variable_id})
end
def get_propagator(%Graph{} = graph, propagator_id) do
case Graph.vertex_labels(graph, propagator_vertex(propagator_id)) do
[] -> nil
[p] -> p
end
end
def update_propagator(
%Graph{vertex_labels: labels, vertex_identifier: identifier} = graph,
propagator_id,
propagator
) do
vertex = propagator_vertex(propagator_id)
graph
|> Map.put(:vertex_labels, Map.put(labels, identifier.(vertex), [propagator]))
end
def propagator_vertex(propagator_id) do
{:propagator, propagator_id}
end
def remove_propagator(graph, propagator_id) do
remove_vertex(graph, propagator_vertex(propagator_id))
end
## Remove variable and all propagators that are isolated points as a result of variable removal
def remove_variable(graph, variable_id) do
remove_vertex(graph, {:variable, variable_id})
end
### Remove fixed variables and update propagators with variable domains.
### Returns updated graph and a list of propagators bound to variable domains
def update(graph, vars) do
## Remove fixed variables
{g1, propagators, variable_map} =
Enum.reduce(vars, {graph, [], Map.new()}, fn %{domain: domain} = v,
{graph_acc, propagators_acc, variables_acc} ->
{if Domain.fixed?(domain) do
remove_variable(graph_acc, v.id)
else
graph_acc
end, propagators_acc ++ get_propagator_ids(graph_acc, v.id, fn _ -> true end),
Map.put(variables_acc, v.id, v)}
end)
## Update domains
Enum.reduce(propagators, {g1, []}, fn p_id, {graph_acc, p_acc} ->
get_propagator(graph_acc, p_id)
|> Propagator.bind_to_variables(variable_map, :domain)
|> then(fn bound_p ->
{
update_propagator(graph_acc, p_id, bound_p),
[bound_p | p_acc]
}
end)
end)
end
def remove_vertex(graph, vertex) do
Graph.delete_vertex(graph, vertex)
end
defp get_propagate_on(variable) do
Map.get(variable, :propagate_on, Propagator.to_domain_events(:fixed))
end
end