5.168. global_contiguity
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Synonym
.
- Argument
- Restrictions
- Purpose
Enforce all variables of the collection to be assigned value 0 or 1. In addition, all variables assigned to value 1 appear contiguously.
- Example
-
The constraint holds since the sequence contains no more than one group of contiguous 1.
- All solutions
FigureΒ 5.168.1 gives all solutions to the following non ground instance of the constraint: , , , , .
Figure 5.168.1. All solutions corresponding to the non ground example of the constraint of the All solutions slot
- Typical
- Symmetry
Items of can be reversed.
- Arg. properties
Contractible wrt. .
- Usage
The articleΒ [Maher02] introducing this constraint refers to hardware configuration problems.
- Algorithm
A filtering algorithm for this constraint is described inΒ [Maher02].
- Counting
-
Length () 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Solutions 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 154 172 191 211 232 254 277 301 Number of solutions for : domains
- See also
common keyword: , Β (sequence).
implies: , , .
related: .
- Keywords
characteristic of a constraint: convex, automaton, automaton without counters, automaton with same input symbol, reified automaton constraint.
combinatorial object: sequence.
constraint network structure: Berge-acyclic constraint network.
- Cond. implications
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph model
Each connected component of the final graph corresponds to one set of contiguous variables that all take value 1.
PartsΒ (A) andΒ (B) of FigureΒ 5.168.2 respectively show the initial and final graph associated with the Example slot. The constraint holds since the final graph does not contain more than one connected component. This connected component corresponds to 2 contiguous variables that are both assigned to 1.
Figure 5.168.2. Initial and final graph of the constraint
(a) (b)
- Automaton
FigureΒ 5.168.3 depicts the automaton associated with the constraint. To each variable of the collection corresponds a signature variable that is equal to . There is no signature constraint.
Figure 5.168.3. Automaton of the constraint
Figure 5.168.4. Hypergraph of the reformulation corresponding to the automaton of the constraint