### 2.3.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 usuallyAnother way of generating several initial graphs will be explained later on in the Arc input(s) slot. achieved by using the $\mathrm{𝙵𝙾𝚁}\mathrm{𝙰𝙻𝙻}\mathrm{𝙸𝚃𝙴𝙼𝚂}\mathrm{𝙾𝙵}$ iterator (e.g., see the definition of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ 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 though 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{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_{1}\left({X}_{1},{X}_{2},\cdots ,{X}_{n}\right)$ and ${\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_{2}\left({X}_{1},{X}_{2},\cdots ,{X}_{n}\right)$ are incompatible if there does not exist any tuple of values $〈{v}_{1},{v}_{2},\cdots ,{v}_{n}〉$ such that both ${\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_{1}\left({X}_{1},{X}_{2},\cdots ,{X}_{n}\right)$ and ${\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_{2}\left({X}_{1},{X}_{2},\cdots ,{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},\cdots ,{C}_{d}$ $\left(d\ge 1\right)$. To each item of these collections corresponds a vertex of the initial graph (i.e., in this context we generate a 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 $\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}_\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}$ constraint.).

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

• $\mathrm{𝐴𝑅𝐶}_\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left({\mathrm{𝚒𝚝𝚎𝚖}}_{1},{\mathrm{𝚒𝚝𝚎𝚖}}_{2},\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_{a}\right)$, where $\mathrm{𝐴𝑅𝐶}_\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}$ is one of the arc generators with a fixed arityAny arc generator different from $\mathrm{𝑃𝐴𝑇𝐻}_\mathit{1}$ and $\mathrm{𝑃𝐴𝑇𝐻}_𝑁$. defined in Section 2.3.2.3 on page 2.3.2.3, and ${\mathrm{𝚒𝚝𝚎𝚖}}_{i}$ $\left(1\le i\le 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.3.2.2.1. which can be used within an arc constraint. When the Arc input(s) slot consists of a single collection $\left(d=1\right)$, ${\mathrm{𝚒𝚝𝚎𝚖}}_{i}$ $\left(1\le i\le a\right)$ represents an item of the collection ${C}_{1}$. Otherwise, when $d>1$, we must have $a=d$ and, in this context, ${\mathrm{𝚒𝚝𝚎𝚖}}_{i}$ $\left(1\le i\le a\right)$ represents an item of ${C}_{i}$.

EXAMPLE: The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$ constraint has the following Arc input(s) and Arc generator slots:

• Its Arc input(s) slot refers only to the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ (i.e., $d=1$).

• Its Arc generator slot consists of

$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$ $\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},$ $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$ (i.e., $a=2$).

In this context, where $d=1$, both $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}$ and $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}$ are items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

EXAMPLE: The $\mathrm{𝚜𝚊𝚖𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right)$ constraint has the following Arc input(s) and Arc generator slots:

• Its Arc input(s) slot refers to the collections $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ and $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ (i.e., $d=2$).

• Its Arc generator slot consists of

$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$ (i.e., $a=2$).

In this context, where $d>1$, $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}$ and $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}$ respectively correspond to items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ and the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ collections.

• $\mathrm{𝐴𝑅𝐶}_\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$, where $\mathrm{𝐴𝑅𝐶}_\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}$ is one of the arc generators $\mathrm{𝑃𝐴𝑇𝐻}_\mathit{1}$ or $\mathrm{𝑃𝐴𝑇𝐻}_𝑁$. In this context, $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$ denotes a collection of items corresponding to the vertices of an arc of the initial graph. An arc constraint forces a restriction on the items of this collection.

EXAMPLE:

The $\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚎𝚚}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ $\left(\mathrm{𝚂𝙸𝚉𝙴},$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$ constraint has the following Arc input(s) and Arc generator slots:

• Its Arc input(s) slot refers to the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

• Its Arc generator slot consists of $\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$.

In this context, $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$ is a collection of the same type as the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ 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{𝐴𝑅𝐶}_{\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}}_{1}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left({\mathrm{𝚒𝚝𝚎𝚖}}_{1},{\mathrm{𝚒𝚝𝚎𝚖}}_{2},\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_{a}\right)$

$\mathrm{𝐴𝑅𝐶}_{\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}}_{2}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left({\mathrm{𝚒𝚝𝚎𝚖}}_{1},{\mathrm{𝚒𝚝𝚎𝚖}}_{2},\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_{a}\right)$

$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$

$\mathrm{𝐴𝑅𝐶}_{\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}}_{n}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left({\mathrm{𝚒𝚝𝚎𝚖}}_{1},{\mathrm{𝚒𝚝𝚎𝚖}}_{2},\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_{a}\right)$

All leftmost part of the expressions must be the same since they will be involved in a single Arc constraint(s) slot. The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢}$ 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{𝚒𝚗𝚝}$, or the character *. In this last case, this is used for denoting 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{𝑃𝐴𝑇𝐻}_\mathit{1}$ or $\mathrm{𝑃𝐴𝑇𝐻}_𝑁$ as in the $\mathrm{𝚊𝚛𝚒𝚝𝚑}_\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}$ or the $\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚎𝚚}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints.

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

• A Graph property(ies) slot, which corresponds to one or several graph properties (see Section 2.3.2.4 on page 2.3.2.4) to be satisfied on the final graphs associated with an instantiated solution to 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{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint, which was introduced as a first example of global constraint that can be modelled by a graph property in Section 2.3.1 on page 2.3.1.

EXAMPLE: The constraint $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$\left(\mathrm{𝙽𝚅𝙰𝙻},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$ restricts $\mathrm{𝙽𝚅𝙰𝙻}$ to be the number of distinct values taken by the variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Its meaning is described by a simple graph constraint corresponding to the following items:

Arc input(s)        :

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator      :

$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity           :

2

Arc constraint(s)   :

$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$

Graph property(ies):

$\mathrm{𝐍𝐒𝐂𝐂}=\mathrm{𝙽𝚅𝙰𝙻}$

Since this description does not use the $\mathrm{𝙵𝙾𝚁}\mathrm{𝙰𝙻𝙻}\mathrm{𝙸𝚃𝙴𝙼𝚂}\mathrm{𝙾𝙵}$ iterator we generate a single initial graph. Each vertex of this graph corresponds to one item of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. Since we use the $\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$ 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{𝙽𝚅𝙰𝙻}$ strongly connected components.

EXAMPLE: The constraint $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$ forces all variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ 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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator      :

$\mathrm{𝑃𝐴𝑇𝐻}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

$\mathrm{𝐿𝑂𝑂𝑃}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity           :

2

Arc constraint(s)   :

$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$

$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathtt{1}$

Graph property(ies):

$\mathrm{𝐍𝐂𝐂}\le 1$

Since this description does not use the $\mathrm{𝙵𝙾𝚁}\mathrm{𝙰𝙻𝙻}\mathrm{𝙸𝚃𝙴𝙼𝚂}\mathrm{𝙾𝙵}$ iterator we generate a single initial graph. Each vertex of this graph corresponds to one item of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. Since we use the $\mathrm{𝑃𝐴𝑇𝐻}$ arc generator we generate an arc from item $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left[i\right]$ to item $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left[i+1\right]$ $\left(1\le i<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\right)$. In addition, since we use the $\mathrm{𝐿𝑂𝑂𝑃}$ arc generator, we generate also an arc from each item of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection to itself.We use the $\mathrm{𝐿𝑂𝑂𝑃}$ 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{𝐍𝐂𝐂}\le 1$ forces to have at most one such group of adjacent variables assigned to 1.

EXAMPLE:

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)$ constraint forces that each value $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚕}$ $\left(1\le i\le |\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|\right)$ be taken by exactly $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. Its meaning is described by a simple graph constraint corresponding to the following items:

For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$:
Arc input(s)        :

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator      :

$\mathrm{𝑆𝐸𝐿𝐹}↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\right)$

Arc arity           :

1

Arc constraint(s)   :

$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$

Graph property(ies):

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$

Since this description uses the For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ iterator on the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection we generate an initial graph for each item of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection (i.e., one graph for each value). Each vertex of an initial graph corresponds to one item of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. Since we use the $\mathrm{𝑆𝐸𝐿𝐹}$ arc generator we have an arc for each vertex. For an initial graph associated with a value $\mathrm{𝑣𝑎𝑙}$ an arc constraint on a vertex $v$ corresponds to an equality constraint between the variable associated with $v$ and the value $\mathrm{𝑣𝑎𝑙}$. Finally, the Graph property(ies) slot forces the final graph to have a given number of vertices (i.e., associated with the attribute $\mathrm{𝑣𝑎𝑙}$).