Package org.jacop.constraints.regular
Class Regular
- java.lang.Object
-
- org.jacop.constraints.DecomposedConstraint<Constraint>
-
- org.jacop.constraints.Constraint
-
- org.jacop.constraints.regular.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 Summary
Fields Modifier and Type Field Description private TimeStamp<java.lang.Integer>[]
activeLevels
Time-stamp for the number of active states in each levelprivate int[]
activeLevelsTemp
private int
calls
This is the counter of save-to-latex calls(package private) java.util.List<Constraint>
constraints
private int
currentTouchedIndex
static boolean
debugAll
It specifies if debugging information should be printed out.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.(package private) 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.(package private) int
firstConsistencyLevel
FSM
fsm
It specifies finite state machine used by this regular.(package private) static java.util.concurrent.atomic.AtomicInteger
idNumber
(package private) int[]
lastNumberOfActiveStates
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"private TimeStamp<java.lang.Integer>
leftChange
The ith smallest level of Layered Graph which have changed.private java.lang.Integer
leftPosition
(package private) boolean[]
levelHadChanged
IntVar[]
list
Array of the variables of the graph levelsboolean
listRepresentation
It specifies if the edges should have a list of values associated with them.(package private) java.util.Map<IntVar,java.lang.Integer>
mapping
boolean
oneSupport
It specifies if the support functionality should be used.boolean
optimizedMDD
It specifies if the translation of FSM into optimized MDD should take place so minimal layered graph can be obtained.private TimeStamp<java.lang.Integer>
rightChange
The ith largest level of Layered Graph which have changed.private java.lang.Integer
rightPosition
static boolean
saveAllToLatex
It specifies if constraint description should be saved to latex for later viewing.private RegState[][]
stateLevels
Stores the states of all graph levels(package private) int
stateNumber
Number of states in the graph used only during the printing to latex functionjava.util.Map<java.lang.Integer,RegEdge>[]
supports
It keeps for each variable value pair a current support.private TimeStamp<java.lang.Integer>
touchedIndex
The position of the currentTouchedIndex(package private) RegState[]
touchedStates
(package private) java.util.LinkedHashSet<IntVar>
variableQueue
-
Fields inherited from class org.jacop.constraints.Constraint
atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace
-
Fields inherited from class org.jacop.constraints.DecomposedConstraint
queueIndex
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addTouchedState(RegState s)
void
consistency(Store store)
It is a (most probably incomplete) consistency function which removes the values from variables domains.java.util.List<Constraint>
decompose(Store store)
It returns an array list of constraint which are used to decompose this constraint.void
disableState(int level, int pos)
It marks state as being not active.int
getDefaultConsistencyPruningEvent()
RegState
getState(int level, int id)
Find the state with the corresponding id.void
impose(Store store)
It imposes the constraint in a given store.void
imposeDecomposition(Store store)
It imposes the decomposition of the given constraint in a given store.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)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)void
pruneArc(int varIndex)
Collects the damaged states, after pruning the domain of variable "var", and put these states in two separated sets.void
queueVariable(int level, Var var)
This is a function called to indicate which variable in a scope of constraint has changed.void
removeLevel(int level)
This function is called in case of the backtrack, so a constraint can clear the queue of changed variables which is no longer valid.void
removeLevelLate(int level)
Sweep the graph upon backtracking.void
saveLatexToFile(java.lang.String desc)
It saves the constraint latex description into file.void
setLatexBaseFileName(java.lang.String filename)
It sets the filename for the file which is used to save latex descriptions.java.lang.String
toLatex(java.lang.String addDescription)
It creates a latex description of the constraint state.java.lang.String
toString()
It produces a string representation of a constraint state.int
unreachBackwardLoop(int sucPrevLimit, int level)
It does backward check to remove inactive edges and states.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.void
uppendToLatexFile(java.lang.String desc, java.lang.String fileName)
It appends latex description of the constraint current state to the specified filename.-
Methods inherited from class org.jacop.constraints.Constraint
afc, arguments, cleanAfterFailure, getConsistencyPruningEvent, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, increaseWeight, intArrayToString, numberArgs, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, updateAFC, watchedVariableGrounded
-
Methods inherited from class org.jacop.constraints.DecomposedConstraint
auxiliaryVariables, checkInput, checkInput, checkInputForDuplication, checkInputForDuplicationSkipSingletons, checkInputForNullness, checkInputForNullness, checkInputForNullness, derivative, getDubletonsSkipSingletons, imposeDecomposition
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface org.jacop.api.Stateful
isStateful
-
-
-
-
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
-
-
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 interfaceStateful
- Parameters:
level
- the level which is being removed.
-
removeLevelLate
public void removeLevelLate(int level)
Sweep the graph upon backtracking.- Specified by:
removeLevelLate
in interfaceRemoveLevelLate
- 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 classConstraint
- 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 classConstraint
- 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 classConstraint
- Parameters:
store
- the constraint store to which the constraint is imposed to.
-
getDefaultConsistencyPruningEvent
public int getDefaultConsistencyPruningEvent()
- Specified by:
getDefaultConsistencyPruningEvent
in classConstraint
-
toString
public java.lang.String toString()
Description copied from class:Constraint
It produces a string representation of a constraint state.- Overrides:
toString
in classConstraint
-
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 classConstraint
- 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 classConstraint
- 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)
-
-