Packages
fixpoint
0.1.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/propagation/propagator.ex
defmodule CPSolver.Propagator do
alias CPSolver.Variable
alias CPSolver.Common
alias CPSolver.Utils
alias CPSolver.Propagator.Variable, as: PropagatorVariable
require Logger
@callback filter(variables :: list()) :: map() | :stable | :failure
@callback variables(args :: list()) :: list()
@domain_changes Common.domain_changes()
defmacro __using__(_) do
quote do
@behaviour CPSolver.Propagator
def variables(args) do
args
end
defoverridable variables: 1
end
end
@behaviour GenServer
## Create a propagator thread; 'propagator' is a tuple {propagator_mod, args} where propagator_mod
## is an implementation of CPSolver.Propagator
##
## Propagator thread is a process that handles life cycle of a propagator.
## TODO: details to follow.
def create_thread(space, propagator, opts \\ [id: make_ref()])
def create_thread(
space,
{propagator_mod, propagator_args} = _propagator,
opts
)
when is_atom(propagator_mod) do
{:ok, _thread} =
GenServer.start_link(__MODULE__, [space, propagator_mod, propagator_args, opts])
end
def create_thread(space, propagator, opts) do
[propagator_mod | args] = Tuple.to_list(propagator)
create_thread(space, {propagator_mod, args}, opts)
end
def dispose(%{thread: pid} = _thread) do
(Process.alive?(pid) && GenServer.stop(pid)) || :not_found
end
## Subscribe propagator thread to variables' events
defp subscribe_to_variables(thread, variables) do
Enum.each(variables, fn var -> subscribe_to_var(thread, var) end)
end
defp subscribe_to_var(thread, variable) do
Utils.subscribe(thread, {:variable, variable.id})
end
defp unsubscribe_from_var(thread, variable) do
Utils.unsubscribe(thread, {:variable, variable})
end
## GenServer callbacks
@impl true
def init([space, propagator_mod, args, opts]) do
bound_vars = Variable.bind_variables(space, propagator_mod.variables(args))
subscribe_to_variables(self(), bound_vars)
propagator_id = Keyword.get(opts, :id, make_ref())
Utils.subscribe(space, {:propagator, propagator_id})
{:ok,
%{
id: propagator_id,
space: space,
propagator_impl: propagator_mod,
args: args,
unfixed_variables:
Enum.reduce(bound_vars, MapSet.new(), fn var, acc ->
(Variable.fixed?(var) && acc) || MapSet.put(acc, var.id)
end),
propagator_opts: opts
}, {:continue, :filter}}
end
@impl true
def handle_continue(:filter, data) do
filter(data)
end
@impl true
def handle_info({:fail, var}, data) do
handle_failure(var, data)
end
def handle_info({:fixed, var}, data) do
new_data = update_unfixed(data, var)
unsubscribe_from_var(self(), var)
if entailed?(new_data) do
handle_entailed(new_data)
else
filter(new_data)
end
end
def handle_info({domain_change, var}, data) when domain_change in @domain_changes do
Logger.debug("#{inspect(data.id)} Propagator: #{inspect(domain_change)} for #{inspect(var)}")
filter(data)
end
### end of GenServer callbacks
defp filter(%{propagator_impl: mod, args: args} = data) do
PropagatorVariable.reset_variable_ops()
case mod.filter(args) do
:stable ->
handle_stable(data)
_res ->
## If propagator doesn't explicitly return 'stable',
## we look into the map of variable operations created by PropagatorVariable wrapper
handle_variable_ops(data)
end
end
defp handle_variable_ops(data) do
case PropagatorVariable.get_variable_ops() do
{:fail, var} ->
handle_failure(var, data)
ops when is_map(ops) ->
{updated_data, no_change} = Enum.reduce(ops, {data, true}, &process_var_ops/2)
cond do
entailed?(updated_data) -> handle_entailed(updated_data)
no_change -> handle_stable(updated_data)
true -> handle_running(updated_data)
end
end
end
defp process_var_ops({var, :fixed}, {data, _} = _acc) do
{update_unfixed(data, var), false}
end
defp process_var_ops({_var, :no_change}, acc) do
acc
end
defp process_var_ops({_var, domain_change}, {data, _} = _acc)
when domain_change in @domain_changes do
{data, false}
end
defp handle_stable(data) do
Logger.debug("#{inspect(data.id)} Propagator is stable")
publish(data, :stable)
{:noreply, data}
end
defp handle_running(data) do
publish(data, :running)
{:noreply, data}
end
defp handle_entailed(data) do
Logger.debug("#{inspect(data.id)} Propagator is entailed (on filtering)")
publish(data, :entailed)
{:stop, :normal, data}
end
def handle_failure(var, data) do
Logger.debug("#{inspect(data.id)} Propagator: Failure for #{inspect(var)}")
publish(data, :failed)
{:stop, :normal, data}
end
defp entailed?(%{unfixed_variables: vars} = _data) do
entailed?(vars)
end
defp entailed?(vars) when is_map(vars) do
MapSet.size(vars) == 0
end
defp update_unfixed(%{unfixed_variables: unfixed} = data, var) do
%{data | unfixed_variables: MapSet.delete(unfixed, var)}
end
defp publish(data, message) do
Utils.publish({:propagator, data.id}, {message, data.id})
end
end