5.166. global_cardinality_no_loop
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
is equal to the number of variables that are assigned value .
The number of assignments of the form () is equal to .
- Example
-
The constraint holds since:
Values 1, 5 and 6 are respectively assigned to the set of variables (i.e.,Β 1 occurrence of value 1), (i.e.,Β no occurrence of value 5) and (i.e.,Β 1 occurrence of value 6). Note that, due to the definition of the constraint, the fact that is assigned to 1 is not counted.
In addition the number of assignments of the form () is equal to .
- Typical
- Symmetry
Items of are permutable.
- Arg. properties
Functional dependency: determined by .
Functional dependency: determined by and .
- Usage
Within the context of the constraint the constraint allows to model a minimum and maximum degree constraint on each vertex of our trees.
- Algorithm
The flow algorithm that handles the original constraintΒ [Regin96] can be adapted to the context of the constraint. This is done by creating an extra value node representing the loops corresponding to the roots of the trees.
- See also
related: Β (graph partitioning by a set of trees with degree restrictions).
root concept: Β (assignment of a to its position is ignored).
specialisation: Β ( replaced by ).
- Keywords
constraint arguments: pure functional dependency.
For all items of :
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
Since, within the context of the first graph constraint, we want to express one unary constraint for each value we use the βFor all items of β iterator. PartΒ (A) of FigureΒ 5.166.1 shows the initial graphs associated with each value 1, 5 and 6 of the collection of the Example slot. PartΒ (B) of FigureΒ 5.166.1 shows the two corresponding final graphs respectively associated with values 1 and 6 that are both assigned to the variables of the collection (since value 5 is not assigned to any variable of the collection the final graph associated with value 5 is empty). Since we use the graph property, the vertices of the final graphs are stressed in bold.
Figure 5.166.1. Initial and final graph of the constraint
(a) (b)