Class Regular

  • All Implemented Interfaces:
    RemoveLevelLate, Stateful, UsesQueueVariable

    public class Regular
    extends Constraint
    implements UsesQueueVariable, Stateful, RemoveLevelLate
    Regular constraint accepts only the assignment to variables which is accepted by an automaton. This constraint implements a polynomial algorithm to establish GAC. There are number of improvements (iterative execution, optimization of computational load upon backtracking) to improve the constraint further.
    Version:
    4.7
    • Field Detail

      • debugAll

        public static final boolean debugAll
        It specifies if debugging information should be printed out.
        See Also:
        Constant Field Values
      • saveAllToLatex

        public static final boolean saveAllToLatex
        It specifies if constraint description should be saved to latex for later viewing.
        See Also:
        Constant Field Values
      • optimizedMDD

        public final boolean optimizedMDD
        It specifies if the translation of FSM into optimized MDD should take place so minimal layered graph can be obtained. This option most of the time causes out of memory exception as it requires finding and storing all solutions in mtrie before translation to an optimized MDD can take place. FSM also has to be a deterministic one.
        See Also:
        Constant Field Values
      • latexFile

        public java.lang.String latexFile
        Name of the file to store the latex output after consistency call The output will be : file_name + "call number" + ".tex"
      • calls

        private int calls
        This is the counter of save-to-latex calls
      • dNames

        public java.util.Map<java.lang.Integer,​java.lang.String> dNames
        dNames contain a "name" for each value from the union of all variabl's domains. If Hashmap - dNames - is not null then upon saving the latex graph the values on the edges will be replaced with their "names".
      • leftChange

        private TimeStamp<java.lang.Integer> leftChange
        The ith smallest level of Layered Graph which have changed.
      • rightChange

        private TimeStamp<java.lang.Integer> rightChange
        The ith largest level of Layered Graph which have changed.
      • touchedIndex

        private TimeStamp<java.lang.Integer> touchedIndex
        The position of the currentTouchedIndex
      • stateLevels

        private RegState[][] stateLevels
        Stores the states of all graph levels
      • activeLevels

        private TimeStamp<java.lang.Integer>[] activeLevels
        Time-stamp for the number of active states in each level
      • activeLevelsTemp

        private int[] activeLevelsTemp
      • stateNumber

        int stateNumber
        Number of states in the graph used only during the printing to latex function
      • variableQueue

        java.util.LinkedHashSet<IntVar> variableQueue
      • mapping

        java.util.Map<IntVar,​java.lang.Integer> mapping
      • idNumber

        static java.util.concurrent.atomic.AtomicInteger idNumber
      • supports

        public java.util.Map<java.lang.Integer,​RegEdge>[] supports
        It keeps for each variable value pair a current support.
      • listRepresentation

        public boolean listRepresentation
        It specifies if the edges should have a list of values associated with them.
      • oneSupport

        public boolean oneSupport
        It specifies if the support functionality should be used.
      • leftPosition

        private java.lang.Integer leftPosition
      • rightPosition

        private java.lang.Integer rightPosition
      • firstConsistencyCheck

        boolean firstConsistencyCheck
        Consistency function call the prune arc function for every pruned variable and collect information about the levels that had some changes in "levelHadChaged" array Then it collect the values of the edges that are still active on the levels that had chages and update the domains of the variables.
      • levelHadChanged

        boolean[] levelHadChanged
      • firstConsistencyLevel

        int firstConsistencyLevel
      • constraints

        java.util.List<Constraint> constraints
      • touchedStates

        RegState[] touchedStates
      • currentTouchedIndex

        private int currentTouchedIndex
      • fsm

        public FSM fsm
        It specifies finite state machine used by this regular.
      • list

        public IntVar[] list
        Array of the variables of the graph levels
      • lastNumberOfActiveStates

        int[] lastNumberOfActiveStates
    • Constructor Detail

      • Regular

        public Regular​(FSM fsm,
                       IntVar[] list)
        Constructor need Store to initialize the time-stamps
        Parameters:
        fsm - (deterministic) finite automaton
        list - variables which values have to be accepted by the automaton.
    • Method Detail

      • initializeARRAY

        private void initializeARRAY​(FSM dfa)
        Initialization phase of the algorithm Considering that it needs to initialize the array of graph States - stateLevels, and, thus, it needs to know the actual number of the states on each level I found nothing better then run the initialization phase with the complete NxN array of states and then copy the useful ones into a final array (which is ugly)
        Parameters:
        dfa -
      • getState

        public RegState getState​(int level,
                                 int id)
        Find the state with the corresponding id.
        Parameters:
        level - specifies the variable for which the state is seeked for.
        id - specifies the id of the state.
        Returns:
        the state at given level with a given id.
      • pruneArc

        public void pruneArc​(int varIndex)
        Collects the damaged states, after pruning the domain of variable "var", and put these states in two separated sets. One with the states with zero incoming degree - these are the candidates for the forward part. The other set consists of states with zero out-coming degree - these are the candidates for backward part.
        Parameters:
        varIndex - the index of the variable which have changed.
      • addTouchedState

        private void addTouchedState​(RegState s)
      • unreachBackwardLoop

        public int unreachBackwardLoop​(int sucPrevLimit,
                                       int level)
        It does backward check to remove inactive edges and states.
        Parameters:
        sucPrevLimit - previous number of states at a given level.
        level - level for which the backward sweep is computed.
        Returns:
        level at which the sweep has ended. TODO return value is not used.
      • unreachForwardLoop

        public void unreachForwardLoop​(int end,
                                       int level)
        Forward part deletes the outgoing edges of the damaged state and watch whether the successors are still active (in-degree > 0 ), otherwise we collect it and continue the loop. TODO return value is not used.
        Parameters:
        end - the position of the last active state at a given level.
        level - level being examined.
      • disableState

        public void disableState​(int level,
                                 int pos)
        It marks state as being not active.
        Parameters:
        level - level at which the state is residing.
        pos - position of the state in the array of states.
      • 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.
      • removeLevelLate

        public void removeLevelLate​(int level)
        Sweep the graph upon backtracking.
        Specified by:
        removeLevelLate in interface RemoveLevelLate
        Parameters:
        level - the level which is being removed.
      • 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.
      • 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.
      • 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.
      • 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
      • imposeDecomposition

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

        public java.util.List<Constraint> decompose​(Store store)
        Description copied from class: Constraint
        It returns an array list of constraint which are used to decompose this constraint. It actually creates a decomposition (possibly also creating variables), but it does not impose the constraint.
        Overrides:
        decompose in class Constraint
        Parameters:
        store - the constraint store in which context the decomposition takes place.
        Returns:
        an array list of constraints used to decompose this constraint.
      • toLatex

        public java.lang.String toLatex​(java.lang.String addDescription)
        It creates a latex description of the constraint state.
        Parameters:
        addDescription - added description.
        Returns:
        description of the constraint state.
      • saveLatexToFile

        public void saveLatexToFile​(java.lang.String desc)
        It saves the constraint latex description into file.
        Parameters:
        desc - description of the constraint
      • setLatexBaseFileName

        public void setLatexBaseFileName​(java.lang.String filename)
        It sets the filename for the file which is used to save latex descriptions.
        Parameters:
        filename - the name of the file
      • uppendToLatexFile

        public void uppendToLatexFile​(java.lang.String desc,
                                      java.lang.String fileName)
        It appends latex description of the constraint current state to the specified filename.
        Parameters:
        desc - appended description.
        fileName - filename where the description is appended.
      • initializeARRAY

        private void initializeARRAY​(MDD mdd)
        Initialization phase of the algorithm Considering that it needs to initialize the array of graph States - stateLevels, and, thus, it needs to know the actual number of the states on each level I found nothing better then run the initialization phase with the complete NxN array of states and then copy the useful ones into a final array (which is ugly)