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.9
  • Field Details

    • debugAll

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

      public static final boolean saveAllToLatex
      It specifies if constraint description should be saved to latex for later viewing.
      See Also:
    • 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:
    • latexFile

      public 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 Map<Integer,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<Integer> leftChange
      The ith smallest level of Layered Graph which have changed.
    • rightChange

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

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

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

      private TimeStamp<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

      LinkedHashSet<IntVar> variableQueue
      Queue of changed variables. TODO try to use PriorityQueue based on the number of states for a given variable or a domain size to pickup first variables which may result in failure faster. It does not have to be fully correct ordering.
    • mapping

      Map<IntVar,Integer> mapping
    • idNumber

      static AtomicInteger idNumber
    • supports

      public Map<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 Integer leftPosition
    • rightPosition

      private 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

      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 Details

    • 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 Details

    • 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 - specification of deterministic finite automaton.
    • 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.
    • getDefaultConsistencyPruningEvent

      public int getDefaultConsistencyPruningEvent()
      Specified by:
      getDefaultConsistencyPruningEvent in class Constraint
    • toString

      public 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 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 String toLatex(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(String desc)
      It saves the constraint latex description into file.
      Parameters:
      desc - description of the constraint
    • setLatexBaseFileName

      public void setLatexBaseFileName(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(String desc, 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)