2.3.2. Ingredients used for describing global constraints

We first introduce the basic ingredients used for describing a global constraint and illustrate them shortly on the example of the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint introduced in the previous section on page 2.3.1. We then go through each basic ingredient in more detail. The graph-based description is founded on the following basic ingredients:

• Data types and restrictions used in order to describe the arguments of a global constraint. Data types and restrictions were already described in the previous section (from page 2.2.1 to page 2.2.4).

• Collection generators used in order to derive new collections from the arguments of a global constraint for one of the following reasons:

  • Collection generators are sometimes required since the initial graph of a global constraint cannot always be directly generated from the arguments of the global constraint. The $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$(\mathrm{𝙽𝚅𝙰𝙻},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})$ constraint did not require any collection generator since the vertices of its initial graph were directly generated from the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

  • A second use of collection generators is for deriving a collection of items for different set of vertices of the final graph. This is sometimes required when we use set generators (see the last item of the enumeration).

• Elementary constraints associated with the arcs of the initial and final graph of a global constraint. The $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint was using an equality constraint, but other constraints are usually required.

• Graph generators employed for constructing the initial graph of a global constraint. In the context of the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint the initial graph was a clique. As we will see later, other patterns are needed for generating an initial graph.

• Graph properties and graph classes used for constraining the final graph we want to obtain. In the context of the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint we were using the number of strongly connected components for counting the number of distinct values.

• Set generators that may be used for generating specific sets of vertices of the final graph on which we want to enforce a given constraint. Since the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint forces a graph property on the final graph (and not on subparts of the final graph) we did not use this feature.

We first start to explain each ingredient separately and then show how one can describe most global constraints in terms of these basic ingredients.

• 2.3.2.1. Collection generators
• 2.3.2.2. Elementary constraints attached to the arcs
• 2.3.2.3. Graph generators
• 2.3.2.4. Graph properties