5.143. 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.
- Typical
- Symmetry
Items of can be reversed.
- Usage
The articleΒ [Maher02] introducing this constraint refers to hardware configuration problems.
- Algorithm
A filtering algorithm for this constraint is described inΒ [Maher02].
- See also
common keyword: , Β (sequence).
implies: , .
related: .
- Keywords
characteristic of a constraint: convex, automaton, automaton without counters, reified automaton constraint.
combinatorial object: sequence.
constraint network structure: Berge-acyclic constraint network.
- 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.143.1 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.143.1. Initial and final graph of the constraint
(a) (b)
- Automaton
FigureΒ 5.143.2 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.143.2. Automaton of the constraint
Figure 5.143.3. Hypergraph of the reformulation corresponding to the automaton of the constraint
