3.5. Constraints argument patterns

If you do not know the name of the global constraint you are looking for, but you know the types of its arguments this section allows to find out all global constraints which have similar arguments. For this purpose we associate to each global constraint of the catalogue a unique normalised signature tree derived from the types of its arguments.An informal rule used in the catalogue about the order of the arguments of a constraint is that we usually first mention a domain variable which represents a result computed from one or several collections that occur just after. Finally, eventual parameters are put as the last arguments of the constraint. The purpose of this normalised signature tree is to get a concise normal form of the arguments of a global constraint that does not depend of the order in which these arguments are defined.

Figure 3.5.1. Illustrating stepsΒ (2), (3) andΒ (4) for computing the normalised signature tree
ctrs/signatures

The normalisation takes as input the slots Type(s) and Argument(s) of the description of a global constraintSee Section 2.1.4 for the description of these slots. and computes the normalised signature tree in four steps:

  1. The first step converts all types related to variables to their corresponding ground counterpart: the types πšπšŸπšŠπš›, πšœπšŸπšŠπš›, πš–πšŸπšŠπš› and πš›πšŸπšŠπš› are respectively transformed to πš’πš—πš, πšœπš’πš—πš, πš–πš’πš—πš and πš›πšŽπšŠπš•.

  2. The second step builds a tree of types 𝒯 by exploring the slot Argument(s) and by developing the compound data types eventually used. The root of this tree is the type πšŠπšπš˜πš– and represents the name of the global constraint.

  3. The third step normalises the tree of types 𝒯 by first normalising each subtree of 𝒯 and then by sorting the children of 𝒯. We assume the following ordering on the different types: πšŠπšπš˜πš–β‰Ίπš’πš—πšβ‰Ίπšœπš’πš—πšβ‰Ίπš–πš’πš—πšβ‰Ίπš›πšŽπšŠπš•β‰Ίπš•πš’πšœπšβ‰ΊπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—. Let 𝒯 n denote the normalised tree obtained at this third step.

  4. Finally the last step tries to reduce the size of the normalised tree 𝒯 n by identifying k(k>1) childrens of a vertex v of 𝒯 n for which the k subtrees are identical. When such a configuration is identified the k subtrees of v are replaced by one single subtree and the integer k is put as an exponent of v.

Table 3.5.1. Example of information associated with a normalised signature tree
ctrs/fig_tree_a_x_c2_x_i_y_y
  1. πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—

  2. πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ

  3. πšπš’πšœπš“πš˜πš’πš—πš

  4. πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš—

  5. πš’πš—πšŸπšŽπš›πšœπšŽ_πš πš’πšπš‘πš’πš—_πš›πšŠπš—πšπšŽ

  6. πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš

  7. πš•πšŽπš‘_πšŽπššπšžπšŠπš•

  8. πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›

  9. πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš

  10. πš•πšŽπš‘_πš•πšŽπšœπšœ

  11. πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš

  12. πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš–

  13. πšœπšŠπš–πšŽ

  14. πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—

  15. πšœπš˜πš›πš

  16. 𝚞𝚜𝚎𝚍_πš‹πš’

  17. 𝚞𝚜𝚎𝚜

  18. 𝚟𝚎𝚌_𝚎𝚚_πšπšžπš™πš•πšŽ


ctrs/fig_tree_a_x_c2_x_i_y_y_

The three rows of FigureΒ 3.5.1 illustrate respectively the second, third and fourth steps for computing the normalised signature tree associated with the arguments of the constraints πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšŒπš‘πšŠπš—πšπšŽ, πšŒπš˜πšžπš—πš, πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ, πšπš’πšπšπš—, πš–πš’πš—πš’πš–πšžπš– and πšœπšŠπš–πšŽ.

The next sections provide for each possible constraints arity all existing normalised signature trees together with the corresponding list of global constraints of the catalogue. The leftmost part of an entry corresponds to a normalised signature tree, while the rightmost upper part gives the corresponding list of global constraints. Finally the rightmost lower part describes the dependency between the constraints of the list: there is an edge from a constraint πšŒπšπš› 1 to a constraint πšŒπšπš› 2 if and only if the fact that πšŒπšπš› 1 holds implies that πšŒπšπš› 2 also holds. For instance, consider the constraints associated with the normalised signature tree corresponding to two collections of integers depicted by TableΒ 3.5.1. There is an edge from 15 (i.e.,Β πšœπš˜πš›πš) to 13 (i.e.,Β πšœπšŠπš–πšŽ) since the fact that a πšœπš˜πš›πš constraint holds implies that a πšœπšŠπš–πšŽ constraint also holds.