Package org.jacop.constraints

Class Alldistinct

  • All Implemented Interfaces:
    SatisfiedPresent, Stateful, UsesQueueVariable
    public class Alldistinct
extends Constraint
implements UsesQueueVariable, Stateful, SatisfiedPresent
    Alldistinct constraint assures that all FDVs have different values.

    This implementation is based on Regin paper. It uses slightly modified Hopcroft-Karp algorithm to compute maximum matching. The value graph is analysed and Tarjan algorithm for finding strongly connected components is used. Maximum matching and Value Graph is stored as TimeStamp Mutable variables to minimize recomputation. Value graph is expensive in terms of memory usage. Use this constraint with care. One variable with domain 0..1000000 will make it use few MB already and kill the efficiency.

    Version:
    4.8

    • Field Detail

      • idNumber

        static java.util.concurrent.atomic.AtomicInteger idNumber

      • backtrackOccured

        boolean backtrackOccured

      • consistencyChecks

        public int consistencyChecks
        It counts the number of executions of the consistency function.

      • fullConsistencyPassesWithNarrowingEvent

        public int fullConsistencyPassesWithNarrowingEvent
        It computes how many times did consistency execution has been re-executed due to narrowing event at the end of the consistency function.

      • freeVariables

        java.util.LinkedHashSet<IntVar> freeVariables

      • impositionFailure

        boolean impositionFailure

      • maximumMatchingNotRecomputed

        boolean maximumMatchingNotRecomputed

      • n

        int n

      • permutationConsistency

        boolean permutationConsistency

      • potentialFreeValues

        java.lang.Integer[] potentialFreeValues

      • scc

        java.util.Map<IntVar,​java.lang.Integer> scc

      • stampNotGroundedVariables

        TimeStamp<java.lang.Integer> stampNotGroundedVariables

      • stampReachability

        TimeStamp<java.lang.Integer> stampReachability

      • stamps

        java.util.Map<java.lang.Integer,​TimeStamp<java.lang.Integer>> stamps

      • stampValues

        TimeStamp<java.lang.Integer> stampValues

      • valueIndex

        java.util.Map<java.lang.Integer,​java.lang.Integer> valueIndex

      • variableQueue

        java.util.LinkedHashSet<IntVar> variableQueue

      • vn

        int vn

      • list

        public IntVar[] list
        It specifies all variables which have to have different values.

      • guideVariable

        IntVar guideVariable

      • guideValue

        int guideValue

      • greedy

        boolean greedy

    • Constructor Detail

      • Alldistinct

        public Alldistinct​(IntVar[] list)
        It constructs an alldistinct constraint.
        Parameters:
        list - an array of variables.

      • Alldistinct

        public Alldistinct​(java.util.List<? extends IntVar> list)
        It constructs an alldistinct constraint.
        Parameters:
        list - arraylist of variables.

    • Method Detail

      • removeLevel

        public void removeLevel​(int level)
        Description copied from interface: Stateful
        This function is called in case of the backtrack, so a constraint can clear the queue of changed variables which is no longer valid. This function is called *before* all timestamps, variables, mutablevariables have reverted to their previous value.
        Specified by:
        removeLevel in interface Stateful
        Parameters:
        level - the level which is being removed.

      • consistency

        public void consistency​(Store store)
        Description copied from class: Constraint
        It is a (most probably incomplete) consistency function which removes the values from variables domains. Only values which do not have any support in a solution space are removed.
        Specified by:
        consistency in class Constraint
        Parameters:
        store - constraint store within which the constraint consistency is being checked.

      • hopcroftKarpMaximumMatching

        private boolean hopcroftKarpMaximumMatching()

      • impose

        public void impose​(Store store)
        Description copied from class: Constraint
        It imposes the constraint in a given store.
        Overrides:
        impose in class Constraint
        Parameters:
        store - the constraint store to which the constraint is imposed to.

      • markReachableVariables

        private void markReachableVariables​(java.util.LinkedHashSet<IntVar> variablesReachableFromFreeValues,
                                    java.lang.Integer value)

      • queueVariable

        public void queueVariable​(int level,
                          Var var)
        Description copied from class: Constraint
        This is a function called to indicate which variable in a scope of constraint has changed. It also indicates a store level at which the change has occurred.
        Overrides:
        queueVariable in class Constraint
        Parameters:
        level - the level of the store at which the change has occurred.
        var - variable which has changed.

      • revisitTarjan

        private void revisitTarjan​(IntVar x,
                           java.util.List<IntVar> l,
                           java.util.Map<IntVar,​java.lang.Integer> dfsnum,
                           java.util.Map<IntVar,​java.lang.Integer> low,
                           java.util.LinkedHashSet<IntVar> fdvs)

      • satisfied

        public boolean satisfied()
        Description copied from interface: SatisfiedPresent
        It checks if the constraint is satisfied. It can return false even if constraint is satisfied but not all variables in its scope are grounded. It needs to return true if all variables in its scope are grounded and constraint is satisfied.

        Implementations of this interface for constraints that are not PrimitiveConstraint may require constraint imposition and consistency check as a requirement to work correctly.

        Specified by:
        satisfied in interface SatisfiedPresent
        Returns:
        true if constraint is possible to verify that it is satisfied.

      • toString

        public java.lang.String toString()
        Description copied from class: Constraint
        It produces a string representation of a constraint state.
        Overrides:
        toString in class Constraint

      • visitTarjan

        private void visitTarjan​(IntVar x,
                         java.util.List<IntVar> l,
                         java.util.Map<IntVar,​java.lang.Integer> dfsnum,
                         java.util.Map<IntVar,​java.lang.Integer> low)

      • getGuideConstraint

        public Constraint getGuideConstraint()
        Description copied from class: Constraint
        It specifies a constraint which if imposed by search will enhance propagation of this constraint.
        Overrides:
        getGuideConstraint in class Constraint
        Returns:
        Constraint enhancing propagation of this constraint.

      • getGuideValue

        public int getGuideValue()
        Description copied from class: Constraint
        This function provides a value which if assigned to a variable returned by getGuideVariable() will enhance propagation of this constraint.
        Overrides:
        getGuideValue in class Constraint
        Returns:
        Value which is a base of enhancing constraint.

      • getGuideVariable

        public Var getGuideVariable()
        Description copied from class: Constraint
        This function provides a variable which assigned a value returned by will enhance propagation of this constraint.
        Overrides:
        getGuideVariable in class Constraint
        Returns:
        Variable which is a base of enhancing constraint.

      • estimatePruning

        int estimatePruning​(IntVar x,
                    java.lang.Integer v)

      • estimatePruningRecursive

        int estimatePruningRecursive​(IntVar xVar,
                             java.lang.Integer v,
                             java.util.List<IntVar> exploredX,
                             java.util.List<java.lang.Integer> exploredV)