2.2.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 constraint introduced in the previous section on page 2.2.1. We then go through each basic ingredient in more detail. The graph -based description is founded on the following basic ingredients:
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 constraint did not require any collection generator since the vertices of its initial graph were directly generated from the 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).
Graph generators employed for constructing the initial graph of a global constraint. In the context of the 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 constraint we were using the number of strongly connected components for expressing the fact that we want to count 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 constraint enforces 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.