Class Propagator<V extends Variable>
- java.lang.Object
-
- org.chocosolver.solver.constraints.Propagator<V>
-
- Type Parameters:
V
- type of variables involved in this propagator
- All Implemented Interfaces:
Comparable<Propagator>
,ICause
,Identity
- Direct Known Subclasses:
AbstractPropDistanceXYZ
,ClauseStore
,ClauseStore.SignedClause
,PropAbsolute
,PropAllDiff
,PropAllDiffAC
,PropAllDiffBC
,PropAllDiffInst
,PropAllDisjoint
,PropAllEqual
,PropAMNV
,PropAmongGAC
,PropAntiArborescences
,PropAtLeastNValues
,PropAtLeastNValues_AC
,PropAtMost1Empty
,PropAtMostNValues
,PropAtMostNValues_BC
,PropBinCSP
,PropBitChanneling
,PropBoolChannel
,PropBoolMax
,PropBoolMin
,PropCardinality
,PropCircuit_ArboFiltering
,PropCircuitSCC
,PropClauseChanneling
,PropCompactTable
,PropCondAllDiff_AC
,PropConditionnal
,PropCostRegular
,PropCount_AC
,PropCountVar
,PropCumulative
,PropDiffN
,PropDistanceXYC
,PropDivXYZ
,PropElement
,PropElement
,PropElementV_fast
,PropEnumDomainChanneling
,PropEqualX_Y
,PropEqualX_YC
,PropEqualXC
,PropEqualXY_C
,PropFalse
,PropFastGCC
,PropGreaterOrEqualX_Y
,PropGreaterOrEqualX_YC
,PropGreaterOrEqualXC
,PropGreaterOrEqualXY_C
,PropIntBoundedMemberSet
,PropIntChannel
,PropIntCstMemberSet
,PropIntCstNotMemberSet
,PropIntEnumMemberSet
,PropIntersection
,PropIntersectionFilterSets
,PropIntValuePrecedeChain
,PropInverse
,PropInverseChannelAC
,PropInverseChannelBC
,PropItemToLoad
,PropKeysorting
,PropKLoops
,PropKnapsack
,PropLargeCSP
,PropLargeMDDC
,PropLessOrEqualXC
,PropLessOrEqualXY_C
,PropLex
,PropLexChain
,PropLexInt
,PropLoadToItem
,PropLocalConDis
,PropMax
,PropMaxBC
,PropMaxElement
,PropMember
,PropMin
,PropMinBC
,PropMinElement
,PropMultiCostRegular
,PropNbEmpty
,PropNogoods
,PropNoSubtour
,PropNotEmpty
,PropNotEqualX_Y
,PropNotEqualX_YC
,PropNotEqualXC
,PropNotEqualXY_C
,PropNotMember
,PropNotMemberIntSet
,PropNotMemberSetInt
,PropOffSet
,PropOpposite
,PropRegular
,PropReif
,PropSat
,PropScalarMixed
,PropScale
,PropSetIntValuesUnion
,PropSignedClause
,PropSort
,PropSquare
,PropSubcircuit
,PropSubcircuitDominatorFilter
,PropSubsetEq
,PropSum
,PropSumOfElements
,PropSymmetric
,PropTableStr2
,PropTimesNaive
,PropTrue
,PropUnion
,PropXeqCReif
,PropXeqYCReif
,PropXinSReif
,PropXltCReif
,PropXltYCReif
,PropXplusYeqZ
,RealPropagator
public abstract class Propagator<V extends Variable> extends Object implements ICause, Identity, Comparable<Propagator>
APropagator
class defines methods to react on aVariable
objects modifications. It is observed byConstraint
objects and can notify them when aVariable
event occurs.
Propagator methods are assumed to be idempotent, ie : Let f be a propagator method, such that f : D -> D' include D, where D the union of variable domains involved in f. Then, f(D)=f(D').
APropagator
declares a filtering algorithm to apply to theVariables
objects in scope in order to reduce theirDomain
objects. That's why thepropagate
method should be adapted to the expected filtering algorithm. This method is called throughConstraint
observers when an event occurs on a scopedVariable
object.propagate
method can throw aContradictionException
when thisPropagator
object detects a contradiction, within its filtering algorithm, like domain wipe out, out of domain value instantiation or other incoherence.
Furthermore, aPropagator
object can be entailed : considering the current state of itsVariable
objects, the internal filtering algorithm becomes useless (for example: NEQ propagator and a couple ofVariable
objects with disjoint domains). In other words, whatever are the future events occurring onVariable
objects, new calls topropagate
method would be useless.
this
can be deactivated using thesetPassive
method. It automatically informsConstraint
observers of this new "state".The developer of a propagator must respect some rules to create a efficient propagator:
- internal references to variables must be achieved referencing thethis.vars
after the call to super, this prevents from wrong references when a variable occurs more than once in the scope (SeePropCount_AC
for instance).
- //to complete- Since:
- 0.01
- Version:
- 0.01, june 2010
- Author:
- Xavier Lorca, Charles Prud'homme, Jean-Guillaume Fages
- See Also:
Variable
,Constraint
-
-
Field Summary
Fields Modifier and Type Field Description protected static short
ACTIVE
Status of the propagator when activated (ie, after initial propagation).protected Constraint
constraint
Encapsuling constraint.static boolean
DEFAULT_EXPL
For debugging purpose only, set to true to use default explanation schema, false to failprotected Model
model
Reference to the model declaring this propagator.protected IOperation[]
operations
Backtrackable operations to maintain the status on backtrack.static boolean
OUTPUT_DEFAULT_EXPL
Set to true to output the name of the constraint that use the default explanation schemaprotected PropagatorPriority
priority
Priority of this propagator.protected boolean
reactToFineEvt
Set to true to indidates that this propagator reacts to fine event.protected short
state
Current status of this propagator.protected V[]
vars
List of variables this propagators deal with.
-
Constructor Summary
Constructors Modifier Constructor Description protected
Propagator(V... vars)
Creates a non-incremental propagator which does not react to fine events but simply calls a coarse propagation any time a variable in vars has changed.protected
Propagator(V[] vars, PropagatorPriority priority, boolean reactToFineEvt)
Creates a new propagator to filter the domains of vars.protected
Propagator(V[] vars, PropagatorPriority priority, boolean reactToFineEvt, boolean swapOnPassivate)
Creates a new propagator to filter the domains of vars.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected void
addVariable(V... nvars)
Enlarges the variable scope of this propagator Should not be called by the user.int
arity()
int
compareTo(Propagator o)
static void
defaultExplain(Propagator prop, ExplanationForSignedClause explanation, ValueSortedMap<IntVar> front, Implications ig, int p)
void
doFinePropagation()
Apply fine event propagation of this.void
doFlush()
Flush pending eventsint
doSchedule(CircularQueue<Propagator>[] queues)
Apply scheduling instructionvoid
doScheduleEvent(int pindice, int mask)
int
dynPriority()
Return the dynamic priority of this propagator.boolean
equals(Object o)
void
explain(ExplanationForSignedClause explanation, ValueSortedMap<IntVar> front, Implications ig, int p)
Clausal explanation for this cause.void
fails()
Throws a contradiction exceptionvoid
forcePropagate(PropagatorEventType evt)
Schedules a coarse propagation to filter all variables at once.protected void
forcePropagationOnBacktrack()
Call this method when either the propagator has to be awake on backtrack.void
forEachIntVar(Consumer<IntVar> action)
Apply an action on each variable declared on the scope of this cause, if any.Constraint
getConstraint()
int
getId()
Model
getModel()
int
getNbVars()
int
getPosition()
PropagatorPriority
getPriority()
int
getPropagationConditions(int vIdx)
Returns the specific mask indicating the variable events on which thisPropagator
object can react.
A mask is a bitwise OR operations overIEventType
this can react on.V
getVar(int i)
Returns the element at the specified position in this internal list ofV
objects.V[]
getVars()
int
getVIndice(int idx)
int[]
getVIndices()
int
hashCode()
boolean
isActive()
boolean
isCompletelyInstantiated()
abstract ESat
isEntailed()
Check wetherthis
is entailed according to the current state of its internal structure.boolean
isPassive()
boolean
isReified()
boolean
isReifiedAndSilent()
boolean
isScheduled()
boolean
isStateLess()
void
linkVariables()
Creates links between this propagator and its variables.abstract void
propagate(int evtmask)
Call the main filtering algorithm to apply to theDomain
of theVariable
objects.void
propagate(int idxVarInProp, int mask)
Incremental filtering algorithm defined within thePropagator
, called whenever the variable of index idxVarInProp has changed.boolean
reactToFineEvent()
BoolVar
reifiedWith()
void
setActive()
informs that this propagator is now active.protected void
setActive0()
void
setPassive()
informs that this propagator is now passive : it holds but no further filtering can occur, so it is useless to propagate it.void
setPosition(int p)
Set the position of this in the propagation engine or -1 if removed.void
setReifiedSilent(BoolVar boolVar)
informs that this reified propagator may not hold.void
setReifiedTrue()
informs that this reified propagator must hold.void
setVIndices(int idx, int val)
Changes the index of a variable in this propagator.String
toString()
void
unlinkVariables()
Destroy links between this propagator and its variables.void
unschedule()
Set this as unscheduled
-
-
-
Field Detail
-
ACTIVE
protected static final short ACTIVE
Status of the propagator when activated (ie, after initial propagation).- See Also:
- Constant Field Values
-
DEFAULT_EXPL
public static boolean DEFAULT_EXPL
For debugging purpose only, set to true to use default explanation schema, false to fail
-
OUTPUT_DEFAULT_EXPL
public static boolean OUTPUT_DEFAULT_EXPL
Set to true to output the name of the constraint that use the default explanation schema
-
state
protected short state
-
operations
protected IOperation[] operations
Backtrackable operations to maintain the status on backtrack.
-
priority
protected final PropagatorPriority priority
Priority of this propagator. Mix between arity and compexity.
-
reactToFineEvt
protected final boolean reactToFineEvt
Set to true to indidates that this propagator reacts to fine event. If set to false, the methodpropagate(int, int)
will never be called.
-
constraint
protected Constraint constraint
Encapsuling constraint.
-
model
protected final Model model
Reference to the model declaring this propagator.
-
-
Constructor Detail
-
Propagator
protected Propagator(V[] vars, PropagatorPriority priority, boolean reactToFineEvt, boolean swapOnPassivate)
Creates a new propagator to filter the domains of vars.
To limit memory consumption, the array of variables is referenced directly (no clone). This is the responsibility of the propagator's developer to take care of that point.- Parameters:
vars
- variables of the propagator. Their modification will trigger filteringpriority
- priority of this propagator (lowest priority propagators are called first)reactToFineEvt
- indicates whether or not this propagator must be informed of every variable modification, i.e. if it should be incremental or notswapOnPassivate
- indicates if, on propagator passivation, the propagator should be ignored in its variables' propagators list.
-
Propagator
protected Propagator(V[] vars, PropagatorPriority priority, boolean reactToFineEvt)
Creates a new propagator to filter the domains of vars.
To limit memory consumption, the array of variables is referenced directly (no clone). This is the responsibility of the propagator's developer to take care of that point.- Parameters:
vars
- variables of the propagator. Their modification will trigger filteringpriority
- priority of this propagator (lowest priority propagators are called first)reactToFineEvt
- indicates whether or not this propagator must be informed of every variable modification, i.e. if it should be incremental or not
-
Propagator
@SafeVarargs protected Propagator(V... vars)
Creates a non-incremental propagator which does not react to fine events but simply calls a coarse propagation any time a variable in vars has changed. This propagator has a regular (linear) priority.- Parameters:
vars
- variables of the propagator. Their modification will trigger filtering
-
-
Method Detail
-
addVariable
@SafeVarargs protected final void addVariable(V... nvars)
Enlarges the variable scope of this propagator Should not be called by the user.- Parameters:
nvars
- variables to be added to this propagator
-
linkVariables
public final void linkVariables()
Creates links between this propagator and its variables. The propagator will then be referenced in each of its variables.
-
unlinkVariables
public final void unlinkVariables()
Destroy links between this propagator and its variables.
-
getPropagationConditions
public int getPropagationConditions(int vIdx)
Returns the specific mask indicating the variable events on which thisPropagator
object can react.
A mask is a bitwise OR operations overIEventType
this can react on. For example, consider a propagator that can deduce filtering based on the lower bound of the integer variable X. Then, for this variable, the mask should be equal to :int mask = IntEventType.INCLOW.getMask() | IntEventType.INSTANTIATE.getMask();
or, in a more convenient way:int mask = IntEvtType.combine(IntEventType.INCLOW,IntEventType.INSTANTIATE);
That indicates the following behavior:- if X is instantiated, this propagator will be executed,
- if the lower bound of X is modified, this propagator will be executed,
- if the lower bound of X is removed, the event is promoted from REMOVE to INCLOW and this propagator will NOT be executed,
- otherwise, this propagator will NOT be executed
IntEventType.VOID
which states that this propagator should not be aware of modifications applied to the variable in position vIdx.- Parameters:
vIdx
- index of the variable within the propagator- Returns:
- an int composed of
REMOVE
and/orINSTANTIATE
and/orDECUPP
and/orINCLOW
-
propagate
public abstract void propagate(int evtmask) throws ContradictionException
Call the main filtering algorithm to apply to theDomain
of theVariable
objects. It considers the current state of this objects to remove some values from domains and/or instantiate some variables. Calling this method is done from 2 (and only 2) steps:
- at the initial propagation step,
- when involved in a reified constraint.
It should initialized the internal data structure and apply filtering algorithm from scratch.- Parameters:
evtmask
- type of propagation eventthis
must consider.- Throws:
ContradictionException
- when a contradiction occurs, like domain wipe out or other incoherencies.
-
propagate
public void propagate(int idxVarInProp, int mask) throws ContradictionException
Incremental filtering algorithm defined within thePropagator
, called whenever the variable of index idxVarInProp has changed. This method calls a CUSTOM_PROPAGATION (coarse-grained) by default.This method should be overridden if the argument
reactToFineEvt
is set totrue
in the constructor. Otherwise, it executespropagate(PropagatorEventType.CUSTOM_PROPAGATION.getStrengthenedMask());
- Parameters:
idxVarInProp
- index of the variablevar
inthis
mask
- type of event- Throws:
ContradictionException
- if a contradiction occurs
-
forcePropagate
public final void forcePropagate(PropagatorEventType evt) throws ContradictionException
Schedules a coarse propagation to filter all variables at once.Add the coarse event recorder into the engine
- Parameters:
evt
- event type- Throws:
ContradictionException
- if the propagation encounters inconsistency.
-
setActive
public void setActive() throws SolverException
informs that this propagator is now active. Should not be called by the user.- Throws:
SolverException
- if the propagator cannot be activated due to its current state
-
setActive0
protected void setActive0()
-
setReifiedTrue
public void setReifiedTrue() throws SolverException
informs that this reified propagator must hold. Should not be called by the user.- Throws:
SolverException
- if the propagator cannot be activated due to its current state
-
setReifiedSilent
public void setReifiedSilent(BoolVar boolVar) throws SolverException
informs that this reified propagator may not hold. Should not be called by the user.- Parameters:
boolVar
- the reifying variable- Throws:
SolverException
- if the propagator cannot be reified due to its current state
-
setPassive
public void setPassive() throws SolverException
informs that this propagator is now passive : it holds but no further filtering can occur, so it is useless to propagate it. Should not be called by the user.- Throws:
SolverException
- if the propagator cannot be set passive due to its current state
-
forcePropagationOnBacktrack
protected void forcePropagationOnBacktrack()
Call this method when either the propagator has to be awake on backtrack. This is helpful when:- the scope of this propagator has changed on failures or solutions (eg. learning clauses)
- this propagator's internal structure has changed (eg. this acts as a cut)
-
isEntailed
public abstract ESat isEntailed()
Check wetherthis
is entailed according to the current state of its internal structure. At least, should check the satisfaction ofthis
(when all is instantiated).- Returns:
- ESat.TRUE if entailed, ESat.FALSE if not entailed, ESat.UNDEFINED if unknown
-
isCompletelyInstantiated
public boolean isCompletelyInstantiated()
- Returns:
- true iff all this propagator's variables are instantiated
-
arity
public int arity()
- Returns:
- the number of uninstantiated variables
-
dynPriority
public int dynPriority()
Return the dynamic priority of this propagator. It excludes from the arity variables instantiated. But may be time consuming.- Returns:
- a more accurate priority excluding instantiated variables.
-
fails
public void fails() throws ContradictionException
Throws a contradiction exception- Throws:
ContradictionException
- expected behavior
-
compareTo
public int compareTo(Propagator o)
- Specified by:
compareTo
in interfaceComparable<V extends Variable>
-
reifiedWith
public BoolVar reifiedWith()
- Returns:
- the boolean variable that reifies this propagator, null otherwise.
-
isReified
public boolean isReified()
- Returns:
- true if this is reified.
Call
reifiedWith()
to get the reifying variable.
-
getModel
public Model getModel()
- Returns:
- the model this propagator is defined in
-
getVar
public final V getVar(int i)
Returns the element at the specified position in this internal list ofV
objects.- Parameters:
i
- index of the element- Returns:
- a
V
object
-
getVars
public final V[] getVars()
- Returns:
- the variable set this propagator holds on. Note that variable multiple occurrence may have lead to variable duplications (i.e. the creation of new variable)
-
getVIndices
public int[] getVIndices()
- Returns:
- the index of the propagator within its variables
-
getVIndice
public int getVIndice(int idx)
- Returns:
- the index of the propagator within its idx^th variable
-
setVIndices
public void setVIndices(int idx, int val)
Changes the index of a variable in this propagator. This method should not be called by the user.- Parameters:
idx
- old indexval
- new index
-
getNbVars
public final int getNbVars()
- Returns:
- the number of variables involved in
this
.
-
getConstraint
public final Constraint getConstraint()
- Returns:
- the constraint including this propagator
-
getPriority
public final PropagatorPriority getPriority()
- Returns:
- the priority of this propagator (may influence the order in which propagators are called)
-
isStateLess
public boolean isStateLess()
- Returns:
- true iff this propagator is stateless: its initial propagation has not been performed yet
-
isReifiedAndSilent
public boolean isReifiedAndSilent()
- Returns:
- true iff this propagator is reified and it is not established yet whether it should hold or not
-
isActive
public boolean isActive()
- Returns:
- true iff this propagator is active (it should filter)
-
isPassive
public boolean isPassive()
- Returns:
- true iff this propagator is passive. This happens when it is entailed : the propagator still hold but no more filtering can occur
-
reactToFineEvent
public final boolean reactToFineEvent()
- Returns:
- true iff the propagator reacts to fine event, that is, it needs to know which variable has been modified and the modification that happened.
-
explain
public void explain(ExplanationForSignedClause explanation, ValueSortedMap<IntVar> front, Implications ig, int p)
Description copied from interface:ICause
Clausal explanation for this cause.This method must filled explanations with inferred literals. These literals are inferred from the analysis of (a subset of) conflicting nodes stored in front, the implication graph ig and the current node in conflict, not yet contained in front.
Optionally, this method can update front by looking for a predecessor of any node that seems more relevant than the declared one.
-
defaultExplain
public static void defaultExplain(Propagator prop, ExplanationForSignedClause explanation, ValueSortedMap<IntVar> front, Implications ig, int p)
-
forEachIntVar
public void forEachIntVar(Consumer<IntVar> action)
Description copied from interface:ICause
Apply an action on each variable declared on the scope of this cause, if any.- Specified by:
forEachIntVar
in interfaceICause
- Parameters:
action
- action to perform on each variable declared in this cause.
-
getPosition
public int getPosition()
- Returns:
- the position of this in the propagation engine
-
setPosition
public void setPosition(int p)
Set the position of this in the propagation engine or -1 if removed.- Parameters:
p
- position of this in the propagation engine or -1 if removed.
-
unschedule
public final void unschedule()
Set this as unscheduled
-
isScheduled
public final boolean isScheduled()
- Returns:
- true if scheduled for propagation
-
doSchedule
public int doSchedule(CircularQueue<Propagator>[] queues)
Apply scheduling instruction- Parameters:
queues
- array of queues in which this can be scheduled- Returns:
- 0 if already scheduled, its priority otherwise
-
doScheduleEvent
public void doScheduleEvent(int pindice, int mask)
-
doFinePropagation
public void doFinePropagation() throws ContradictionException
Apply fine event propagation of this. It iterates over pending modified variables and run propagation on each of them.- Throws:
ContradictionException
- if a contradiction occurred.
-
doFlush
public void doFlush()
Flush pending events
-
-