Class Propagator<V extends Variable>

    • 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
      • 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 method propagate(int, int) will never be called.
      • constraint

        protected Constraint constraint
        Encapsuling constraint.
      • model

        protected final Model model
        Reference to the model declaring this propagator.
      • vars

        protected V extends Variable[] vars
        List of variables this propagators deal with. A variable can occur more than once, but it is considered then as n distinct variables.
    • 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 filtering
        priority - 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
        swapOnPassivate - 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 filtering
        priority - 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 this Propagator object can react.
        A mask is a bitwise OR operations over IEventType 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:
        1. if X is instantiated, this propagator will be executed,
        2. if the lower bound of X is modified, this propagator will be executed,
        3. if the lower bound of X is removed, the event is promoted from REMOVE to INCLOW and this propagator will NOT be executed,
        4. otherwise, this propagator will NOT be executed
        Some combinations are valid. For example, a propagator which reacts on REMOVE and INSTANTIATE should also declare INCLOW and DECUPP as conditions. Indeed INCLOW (resp. DECUPP), for efficiency purpose, removing the lower bound (resp. upper bound) of an integer variable will automatically be promoted into INCLOW (resp. DECUPP). So, ignoring INCLOW and/or DECUPP in that case may result in a lack of filtering. The same goes with events of other variable types, but most of the time, there are only few combinations. Reacts to any kind of event by default. Alternatively, this method can return 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/or INSTANTIATE and/or DECUPP and/or INCLOW
      • propagate

        public abstract void propagate​(int evtmask)
                                throws ContradictionException
        Call the main filtering algorithm to apply to the Domain of the Variable 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 event this 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 the Propagator, 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 to true in the constructor. Otherwise, it executes propagate(PropagatorEventType.CUSTOM_PROPAGATION.getStrengthenedMask());

        Parameters:
        idxVarInProp - index of the variable var in this
        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 wether this is entailed according to the current state of its internal structure. At least, should check the satisfaction of this (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.
      • 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.
      • getId

        public int getId()
        Specified by:
        getId in interface Identity
      • getModel

        public Model getModel()
        Returns:
        the model this propagator is defined in
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class Object
      • getVar

        public final V getVar​(int i)
        Returns the element at the specified position in this internal list of V 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 index
        val - 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.

        Specified by:
        explain in interface ICause
        Parameters:
        explanation - explanation to compute
        front - ordered map of (variable,node> in the conflict frontier of the implication graph.
        ig - an implication graph
        p - the pivot node out of front
      • 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 interface ICause
        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:
        propagator priority
      • 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