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,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,PropMemberBound,PropMemberEnum,PropMin,PropMinBC,PropMinElement,PropMultiCostRegular,PropNbEmpty,PropNogoods,PropNoSubtour,PropNotEmpty,PropNotEqualX_Y,PropNotEqualX_YC,PropNotEqualXC,PropNotEqualXY_C,PropNotMemberBound,PropNotMemberEnum,PropNotMemberIntSet,PropNotMemberSetInt,PropOffSet,PropOpposite,PropRegular,PropReif,PropSat,PropScalarMixed,PropScale,PropSetIntValuesUnion,PropSort,PropSquare,PropSubcircuit,PropSubcircuitDominatorFilter,PropSubsetEq,PropSum,PropSumOfElements,PropSymmetric,PropTableStr2,PropTimesNaive,PropTrue,PropUnion,PropXeqCReif,PropXeqYReif,PropXgtCReif,PropXinSReif,PropXltCReif,PropXltYCReif,PropXltYReif,PropXneCReif,PropXneYReif,PropXplusYeqZ,RealPropagator
public abstract class Propagator<V extends Variable> extends Object implements ICause, Identity, Comparable<Propagator>
APropagatorclass defines methods to react on aVariableobjects modifications. It is observed byConstraintobjects and can notify them when aVariableevent 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').
APropagatordeclares a filtering algorithm to apply to theVariablesobjects in scope in order to reduce theirDomainobjects. That's why thepropagatemethod should be adapted to the expected filtering algorithm. This method is called throughConstraintobservers when an event occurs on a scopedVariableobject.propagatemethod can throw aContradictionExceptionwhen thisPropagatorobject detects a contradiction, within its filtering algorithm, like domain wipe out, out of domain value instantiation or other incoherence.
Furthermore, aPropagatorobject can be entailed : considering the current state of itsVariableobjects, the internal filtering algorithm becomes useless (for example: NEQ propagator and a couple ofVariableobjects with disjoint domains). In other words, whatever are the future events occurring onVariableobjects, new calls topropagatemethod would be useless.
thiscan be deactivated using thesetPassivemethod. It automatically informsConstraintobservers 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.varsafter the call to super, this prevents from wrong references when a variable occurs more than once in the scope (SeePropCount_ACfor 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 ConstraintconstraintEncapsuling constraint.protected ModelmodelReference to the model declaring this propagator.protected PropagatorPrioritypriorityPriority of this propagator.protected booleanreactToFineEvtSet to true to indidates that this propagator reacts to fine event.protected V[]varsList of variables this propagators deal with.
-
Constructor Summary
Constructors Modifier Constructor Description protectedPropagator(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.protectedPropagator(V[] vars, PropagatorPriority priority, boolean reactToFineEvt)Creates a new propagator to filter the domains of vars.protectedPropagator(V[] vars, PropagatorPriority priority, boolean reactToFineEvt, boolean swapOnPassivate)Creates a new propagator to filter the domains of vars.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected voidaddVariable(V... nvars)Enlarges the variable scope of this propagator Should not be called by the user.intarity()intcompareTo(Propagator o)voiddoFinePropagation()Apply fine event propagation of this.voiddoFlush()Flush pending eventsintdoSchedule(CircularQueue<Propagator>[] queues)Apply scheduling instructionvoiddoScheduleEvent(int pindice, int mask)intdynPriority()Return the dynamic priority of this propagator.booleanequals(Object o)voidfails()Throws a contradiction exceptionvoidforcePropagate(PropagatorEventType evt)Schedules a coarse propagation to filter all variables at once.protected voidforcePropagationOnBacktrack()Call this method when either the propagator has to be awake on backtrack.ConstraintgetConstraint()intgetId()ModelgetModel()intgetNbVars()intgetPosition()PropagatorPrioritygetPriority()intgetPropagationConditions(int vIdx)Returns the specific mask indicating the variable events on which thisPropagatorobject can react.
A mask is a bitwise OR operations overIEventTypethis can react on.VgetVar(int i)Returns the element at the specified position in this internal list ofVobjects.V[]getVars()intgetVIndice(int idx)int[]getVIndices()inthashCode()booleanisActive()booleanisCompletelyInstantiated()abstract ESatisEntailed()Check wetherthisis entailed according to the current state of its internal structure.booleanisPassive()booleanisReifiedAndSilent()booleanisStateLess()voidlinkVariables()Creates links between this propagator and its variables.abstract voidpropagate(int evtmask)Call the main filtering algorithm to apply to theDomainof theVariableobjects.voidpropagate(int idxVarInProp, int mask)Incremental filtering algorithm defined within thePropagator, called whenever the variable of index idxVarInProp has changed.booleanreactToFineEvent()voidsetActive()informs that this propagator is now active.voidsetPassive()informs that this propagator is now passive : it holds but no further filtering can occur, so it is useless to propagate it.voidsetPosition(int p)Set the position of this in the propagation engine or -1 if removed.voidsetReifiedSilent()informs that this reified propagator may not hold.voidsetReifiedTrue()informs that this reified propagator must hold.voidsetVIndices(int idx, int val)Changes the index of a variable in this propagator.StringtoString()voidunlinkVariables()Destroy links between this propagator and its variables.voidunschedule()Set this as unscheduledbooleanwhy(RuleStore ruleStore, IntVar var, IEventType evt, int value)Add new rules to the rule store
-
-
-
Field Detail
-
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 thisPropagatorobject can react.
A mask is a bitwise OR operations overIEventTypethis 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.VOIDwhich 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
REMOVEand/orINSTANTIATEand/orDECUPPand/orINCLOW
-
propagate
public abstract void propagate(int evtmask) throws ContradictionExceptionCall the main filtering algorithm to apply to theDomainof theVariableobjects. 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 eventthismust consider.- Throws:
ContradictionException- when a contradiction occurs, like domain wipe out or other incoherencies.
-
propagate
public void propagate(int idxVarInProp, int mask) throws ContradictionExceptionIncremental 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
reactToFineEvtis set totruein the constructor. Otherwise, it executespropagate(PropagatorEventType.CUSTOM_PROPAGATION.getStrengthenedMask());- Parameters:
idxVarInProp- index of the variablevarinthismask- 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 SolverExceptioninforms 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
-
setReifiedTrue
public void setReifiedTrue() throws SolverExceptioninforms 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() throws SolverExceptioninforms that this reified propagator may not hold. Should not be called by the user.- Throws:
SolverException- if the propagator cannot be reified due to its current state
-
setPassive
public void setPassive() throws SolverExceptioninforms 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 wetherthisis 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 ContradictionExceptionThrows a contradiction exception- Throws:
ContradictionException- expected behavior
-
compareTo
public int compareTo(Propagator o)
- Specified by:
compareToin interfaceComparable<V extends 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 ofVobjects.- Parameters:
i- index of the element- Returns:
- a
Vobject
-
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.
-
why
public boolean why(RuleStore ruleStore, IntVar var, IEventType evt, int value)
Description copied from interface:ICauseAdd new rules to the rule store
-
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
-
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 ContradictionExceptionApply 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
-
-