### 2.2.3.1. Simple graph constraint

To a simple graph constraint correspond several initial graphs, usually one, where all the initial graphs have the same vertices and arcs. Specifying more than one initial graph is usuallyAn other way of generating several initial graphs will be explained later on in the Arc input(s) slot. achieved by using the $\mathrm{\pi ΅\pi Ύ\pi }\mathrm{\pi °\pi »\pi »}\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }\mathrm{\pi Ύ\pi ΅}$ iterator (e.g.,Β see for instance the definition of the $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$ constraint), which takes a collection $C$ and generates an initial graph ${G}_{i}\left(t\right)$ for each item $t$ of $C$. In this context, the arc constraints and/or graph properties of an initial graph may depend of the attributes of the item $t$ of $C$ from which they were generated. All arc constraints attached to a given arcAs we previously said, even if we have more than one initial graph, all vertices and arcs of the different initial graphs are identical. have to be pairwise mutually incompatible.Two arc constraints ${\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }}_{1}\left({X}_{1},{X}_{2},...,{X}_{n}\right)$ and ${\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }}_{2}\left({X}_{1},{X}_{2},...,{X}_{n}\right)$ are incompatible if there does not exist any tuple of values $\beta ©{v}_{1},{v}_{2},...,{v}_{n}\beta ͺ$ such that both ${\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }}_{1}\left({X}_{1},{X}_{2},...,{X}_{n}\right)$ and ${\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }}_{2}\left({X}_{1},{X}_{2},...,{X}_{n}\right)$ hold.

The graphs of a simple graph constraint are defined by the following slots:

• An Arc input(s) slot, which consists of:

• Either a sequence of collections ${C}_{1},{C}_{2},...,{C}_{d}$ $\left(d\beta ₯1\right)$. To each item of these collections corresponds a vertex of the initial graph (i.e.,Β in this context we generate one single initial graph).

• Either a list of sequences of collections. To each item of the collections of a given sequence corresponds a vertex of one of the initial graphs (i.e.,Β in this context we generate one initial graph for each sequence This is for instance the case for the constraint.).

• An Arc generator slot, which can be one or several expressionsUsually one single expression. of the following forms:

• $\mathrm{\pi ΄\pi  \pi Ά}_\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({\mathrm{\pi \pi \pi \pi }}_{1},{\mathrm{\pi \pi \pi \pi }}_{2},...,{\mathrm{\pi \pi \pi \pi }}_{a}\right)$, where $\mathrm{\pi ΄\pi  \pi Ά}_\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }$ is one of the arc generators with a fixed arity defined in SectionΒ 2.2.2.3 on page 2.2.2.3, and ${\mathrm{\pi \pi \pi \pi }}_{i}$ $\left(1\beta €i\beta €a\right)$ denotes the ${i}^{th}$ item associated with the ${i}^{th}$ vertex of an arc. These items correspond to formal parametersSee the description of simple arithmetic expressions page 2.2.2.2.1. which can be used within an arc constraint. When the Arc input(s) slot consists of one single collection $\left(d=1\right)$, ${\mathrm{\pi \pi \pi \pi }}_{i}$ $\left(1\beta €i\beta €a\right)$ represents an item of the collection ${C}_{1}$. Otherwise, when $d>1$, we must have $a=d$ and, in this context, ${\mathrm{\pi \pi \pi \pi }}_{i}$ $\left(1\beta €i\beta €a\right)$ represents an item of ${C}_{i}$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ constraint has the following Arc input(s) and Arc generator slots:

• Its Arc input(s) slot refers only to the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ (i.e.,Β $d=1$).

• Its Arc generator slot consists of

$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ $\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$ (i.e.,Β $a=2$).

In this context, where $d=1$, both $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}$ and $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}$ are items of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$ constraint has the following Arc input(s) and Arc generator slots:

• Its Arc input(s) slot refers to the collections $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ (i.e.,Β $d=2$).

• Its Arc generator slot consists of

$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$ (i.e.,Β $a=2$).

In this context, where $d>1$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}$ and $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}$ respectively correspond to items of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ collections.

• $\mathrm{\pi ΄\pi  \pi Ά}_\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, where $\mathrm{\pi ΄\pi  \pi Ά}_\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }$ is one of the arc generators $\mathrm{\pi \pi ΄\pi \pi »}_\mathit{1}$ or $\mathrm{\pi \pi ΄\pi \pi »}_\mathrm{\pi }$. In this context, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ denotes a collection of items corresponding to the vertices of an arc of the initial graph. An arc constraint enforces a restriction on the items of this collection.

EXAMPLE:

The $\mathrm{\pi \pi \pi £\pi }_\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ $\left(\mathrm{\pi \pi Έ\pi \pi ΄},$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ constraint has the following Arc input(s) and Arc generator slots:

• Its Arc input(s) slot refers to the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

• Its Arc generator slot consists of $\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$.

In this context, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ is a collection of the same type as the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. It corresponds to the variables associated with an arc of the initial graph.

When the Arc generator slot consists of $n$ $\left(n>1\right)$ expressions then these expressions have the form:

$\mathrm{\pi ΄\pi  \pi Ά}_{\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }}_{1}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({\mathrm{\pi \pi \pi \pi }}_{1},{\mathrm{\pi \pi \pi \pi }}_{2},...,{\mathrm{\pi \pi \pi \pi }}_{a}\right)$

$\mathrm{\pi ΄\pi  \pi Ά}_{\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }}_{2}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({\mathrm{\pi \pi \pi \pi }}_{1},{\mathrm{\pi \pi \pi \pi }}_{2},...,{\mathrm{\pi \pi \pi \pi }}_{a}\right)$

$...............................................................$

$\mathrm{\pi ΄\pi  \pi Ά}_{\mathrm{\pi Ί\pi Έ\pi \pi Έ\pi  \pi ΄\pi \pi \pi  }}_{n}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left({\mathrm{\pi \pi \pi \pi }}_{1},{\mathrm{\pi \pi \pi \pi }}_{2},...,{\mathrm{\pi \pi \pi \pi }}_{a}\right)$

All leftmost part of the expressions must be the same since they will be involved in one single Arc constraint(s) slot. The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$ constraint is an example of global constraint where more than one arc generator is used.

• An Arc arity slot, which corresponds to the number of vertices $a$ of each arc of the initial graph. $a$ is either a strictly positive integer, an argument of the global constraint of type $\mathrm{\pi \pi \pi }$, or the character *. In this last case, this is used for denoting the fact that all the arc constraints do not involve the same number of vertices. This is for instance the case when we use the arc generators $\mathrm{\pi \pi ΄\pi \pi »}_\mathit{1}$ or $\mathrm{\pi \pi ΄\pi \pi »}_\mathrm{\pi }$ as in the $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ or the $\mathrm{\pi \pi \pi £\pi }_\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints.

• An Arc constraint(s) slot, which corresponds to a conjunction of arc constraintsUsually this conjunction consists of one single arc constraint. those were introduced in SectionΒ 2.2.2.2 on page 2.2.2.2.

• A Graph property(ies) slot, which corresponds to one or several graph properties (see SectionΒ 2.2.2.4 on page 2.2.2.4) to be satisfied on the final graphs associated with an instantiated solution of the global constraint. To each initial graph corresponds one final graph obtained by removing all arcs for which the corresponding arc constraints do not hold as well as all vertices that do not have any arc.

We now give several examples of descriptions of simple graph constraints, starting from the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint, which was introduced as a first example of global constraint that can be modelled by a graph property in SectionΒ 2.2.1 on page 2.2.1.

EXAMPLE: The constraint $\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi  \pi °\pi »},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ restricts $\mathrm{\pi ½\pi  \pi °\pi »}$ to be the number of distinct values taken by the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. Its meaning is described by a simple graph constraint corresponding to the following items:

Arc input(s)Β Β Β Β Β Β Β Β :

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generatorΒ Β Β Β Β Β :

$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arityΒ Β Β Β Β Β Β Β Β Β Β :

2

Arc constraint(s)Β Β Β :

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$

Graph property(ies):

$\mathrm{\pi \pi \pi \pi }=\mathrm{\pi ½\pi  \pi °\pi »}$

Since this description does not use the $\mathrm{\pi ΅\pi Ύ\pi }\mathrm{\pi °\pi »\pi »}\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }\mathrm{\pi Ύ\pi ΅}$ iterator we generate one single initial graph. Each vertex of this graph corresponds to one item of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. Since we use the $\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$ arc generator we have an arc between each pair of vertices. An arc constraint corresponds to an equality constraint between the two variables that are associated with the extremities of the arc. Finally, the Graph property(ies) slot forces the final graph to have $\mathrm{\pi ½\pi  \pi °\pi »}$ strongly connected components.

EXAMPLE: The constraint $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ forces all variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection to be assigned to 0 or 1. In addition, all variables assigned to value 1 appear contiguously. Its meaning is described by a simple graph constraint corresponding to the following items:

Arc input(s)Β Β Β Β Β Β Β Β :

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generatorΒ Β Β Β Β Β :

$\mathrm{\pi \pi ΄\pi \pi »}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β

$\mathrm{\pi Ώ\pi \pi \pi }\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arityΒ Β Β Β Β Β Β Β Β Β Β :

2

Arc constraint(s)Β Β Β :

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathtt{1}$

Graph property(ies):

$\mathrm{\pi \pi \pi }\beta €1$

Since this description does not use the $\mathrm{\pi ΅\pi Ύ\pi }\mathrm{\pi °\pi »\pi »}\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }\mathrm{\pi Ύ\pi ΅}$ iterator we generate one single initial graph. Each vertex of this graph corresponds to one item of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. Since we use the $\mathrm{\pi \pi ΄\pi \pi »}$ arc generator we generate an arc from item $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left[i\right]$ to item $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left[i+1\right]$ $\left(1\beta €i<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\right)$. In addition, since we use the $\mathrm{\pi Ώ\pi \pi \pi }$ arc generator, we generate also an arc from each item of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection to itself.We use the $\mathrm{\pi Ώ\pi \pi \pi }$ arc generator in order to keep in the final graph those isolated variables assigned to 1. This is because isolated vertices with no arcs are always removed from the final graph. The effect of the arc constraint is to keep in the final graph those vertices for which the corresponding variable is assigned to 1. Adjacent variables assigned to 1 form a connected component of the final graph and the graph property $\mathrm{\pi \pi \pi }\beta €1$ enforces to have at most one such group of adjacent variables assigned to 1.

EXAMPLE:

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$ constraint enforces that each value $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi }$ $\left(1\beta €i\beta €|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|\right)$ be taken by exactly $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. Its meaning is described by a simple graph constraint corresponding to the following items:

For all items of $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$:
Arc input(s)Β Β Β Β Β Β Β Β :

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generatorΒ Β Β Β Β Β :

$\mathrm{\pi \pi Έ\pi Ώ\pi Ή}\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\right)$

Arc arityΒ Β Β Β Β Β Β Β Β Β Β :

1

Arc constraint(s)Β Β Β :

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }=\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$

Graph property(ies):

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }=\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$

Since this description uses the For all items of $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ iterator on the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection we generate an initial graph for each item of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection (i.e.,Β one graph for each value). Each vertex of an initial graph corresponds to one item of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. Since we use the $\mathrm{\pi \pi Έ\pi Ώ\pi Ή}$ arc generator we have an arc for each vertex. For an initial graph associated with a value $\mathrm{\pi £\pi \pi }$ an arc constraint on a vertex $v$ corresponds to an equality constraint between the variable associated with $v$ and the value $\mathrm{\pi £\pi \pi }$. Finally, the Graph property(ies) slot forces the final graph to have a given number of vertices (i.e.,Β associated with the attribute $\mathrm{\pi £\pi \pi }$).