Class GCC
- All Implemented Interfaces:
SatisfiedPresent
,Stateful
,UsesQueueVariable
We would like to thank Irit Katriel for making the code of GCC in C she wrote available to us.
- Version:
- 4.9
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
private static class
-
Field Summary
FieldsModifier and TypeFieldDescriptionFix suggested by Radek: a set that keeps track of the variables that have changed and need to be revisited in the consistency methodprivate Comparator
<GCC.XDomain> private int[]
protected IntVar[]
It species variables counters for counting occurences of each possible value from the intial domain of x variables.private static final boolean
private int[]
(package private) boolean
TODO An improvement to increase the incrementality even further.(package private) int
(package private) static AtomicInteger
private int[]
The array which stores the first computed matching, which may not take into account the lower bound of count variables.private int[]
private int[]
The array which stores the second computed matching, which may not take into account the upper bound of count variables.private int[]
private int[]
The array which stores the third proper matching, constructed from the first one and second one so both lower and upper bounds are respected.private int[]
private PriorityQueue
<Integer> private PriorityQueue
<GCC.XDomain> private PriorityQueue
<GCC.XDomain> private ArrayDeque
<Integer> private ArrayDeque
<GCC.Component> private Comparator
<Integer> private Comparator
<GCC.XDomain> private int
IntVar[]
It specifies variables x whose values are counted.private GCC.XDomain[]
private int
private int[][]
private int
Fields inherited from class org.jacop.constraints.Constraint
afcWeight, atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace, watchedVariableGrounded
Fields inherited from class org.jacop.constraints.DecomposedConstraint
queueIndex
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
private boolean
private boolean
private boolean
A method to be called in asserts that checks whether all grounded X variables are correctly put at the end of the listvoid
consistency
(Store store) It is a (most probably incomplete) consistency function which removes the values from variables domains.private void
countBoundConsistency
(Store store) private void
private int
findPosition
(int value, int[] values) private void
int
void
It imposes the constraint in a given store.private void
lowerCount
(int[] min_l) private void
putToTheEnd
(IntVar[] list, int element) void
queueVariable
(int level, Var var) This is a function called to indicate which variable in a scope of constraint has changed.private void
ReachedFromY
(int[] yReachesLeft, int[] yReachesRight) 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.private IntVar[]
removeZeroCounters
(IntVar[] x, IntVar[] counters) boolean
It checks if the constraint is satisfied.private void
SCCs()
private int
SCCsWithoutS
(int[] compReachesLeft, int[] compReachesRight, int[] yReachesLeft, int[] yReachesRight) private void
private void
private void
toString()
It produces a string representation of a constraint state.private void
upperCount
(int[] max_u) Methods inherited from class org.jacop.constraints.Constraint
afc, arguments, cleanAfterFailure, decompose, getConsistencyPruningEvent, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, imposeDecomposition, increaseWeight, intArrayToString, long2int, numberArgs, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, toInt, toInt, 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 Details
-
firstConsistencyCheck
boolean firstConsistencyCheckTODO An improvement to increase the incrementality even further.1. The first matching uses minimal values. Remember which minimal value has changed which removed from the domain the value which was used in the matching. Reuse from old matching 1 all values smaller than the minimal which has changed.
Similar principle applies to matching 2 (skip the positions (variables) until the first index for which m1 did change or for which the m2 value is no longer in the domain.
2. Use IndexDomainView instead of local solution.
3. boolean variable first - is it only once in the consistency function? Then this functionality can be moved out of the while(newPropagation), if it should be executed every time consistency is executed then (it should be setup to true somewhere).
-
idNumber
-
match1
private int[] match1The array which stores the first computed matching, which may not take into account the lower bound of count variables. -
match2
private int[] match2The array which stores the second computed matching, which may not take into account the upper bound of count variables. -
match3
private int[] match3The array which stores the third proper matching, constructed from the first one and second one so both lower and upper bounds are respected. -
match1XOrder
private int[] match1XOrder -
match2XOrder
private int[] match2XOrder -
nbOfMatchPerY
private int[] nbOfMatchPerY -
compOfY
private int[] compOfY -
xDomain
-
yDomain
private int[][] yDomain -
xSize
private int xSize -
ySize
private int ySize -
S1
-
S2
-
pFirst
-
pSecond
-
pCount
-
debug
private static final boolean debug- See Also:
-
domainHash
private int[] domainHash -
xNodesHash
-
xVariableToChange
-
stamp
-
stampValue
private int stampValue -
firstConsistencyLevel
int firstConsistencyLevel -
x
It specifies variables x whose values are counted. -
counters
It species variables counters for counting occurences of each possible value from the intial domain of x variables. -
compareLowerBound
-
sortPriorityMinOrder
-
sortPriorityMaxOrder
-
zeroCounters
-
changedVariables
Fix suggested by Radek: a set that keeps track of the variables that have changed and need to be revisited in the consistency method
-
-
Constructor Details
-
GCC
It constructs global cardinality constraint.- Parameters:
x
- variables which values are counted.counters
- variables which count the values.
-
GCC
It constructs global cardinality constraint.- Parameters:
x
- variables which values are counted.counters
- variables which count the values.
-
-
Method Details
-
removeZeroCounters
-
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.
-
consistency
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.
-
checkXorder
private boolean checkXorder()A method to be called in asserts that checks whether all grounded X variables are correctly put at the end of the list- Returns:
- false if the X variable order is inconsistent
-
getDefaultConsistencyPruningEvent
public int getDefaultConsistencyPruningEvent()- Specified by:
getDefaultConsistencyPruningEvent
in classConstraint
-
impose
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.
-
queueVariable
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.
-
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 interfaceSatisfiedPresent
- Returns:
- true if constraint is possible to verify that it is satisfied.
-
toString
Description copied from class:Constraint
It produces a string representation of a constraint state.- Overrides:
toString
in classConstraint
-
FindGeneralizedMatching
private void FindGeneralizedMatching() -
checkFirstPass
private boolean checkFirstPass() -
checkSecondPass
private boolean checkSecondPass() -
checkThirdPass
private boolean checkThirdPass() -
firstPass
private void firstPass() -
secondPass
private void secondPass() -
thirdPass
private void thirdPass() -
SCCs
private void SCCs() -
SCCsWithoutS
private int SCCsWithoutS(int[] compReachesLeft, int[] compReachesRight, int[] yReachesLeft, int[] yReachesRight) -
ReachedFromY
private void ReachedFromY(int[] yReachesLeft, int[] yReachesRight) -
putToTheEnd
-
countBoundConsistency
-
upperCount
private void upperCount(int[] max_u) -
lowerCount
private void lowerCount(int[] min_l) -
sortXByDomainMin
private void sortXByDomainMin() -
findPosition
private int findPosition(int value, int[] values)
-