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(X_1,X_2,\cdots ,X_n)$ and ${\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_2(X_1,X_2,\cdots ,X_n)$ are incompatible if there does not exist any tuple of values $\langle v_1,v_2,\cdots ,v_n\rangle$ such that both ${\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_1(X_1,X_2,\cdots ,X_n)$ and ${\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}}_2(X_1,X_2,\cdots ,X_n)$ 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$ $(d\ge 1)$. 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{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}\mapsto \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}({\mathrm{𝚒𝚝𝚎𝚖}}_1,{\mathrm{𝚒𝚝𝚎𝚖}}_2,\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_a)$, 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$ $(1\le i\le a)$ 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 $(d=1)$, ${\mathrm{𝚒𝚝𝚎𝚖}}_i$ $(1\le i\le a)$ represents an item of the collection $C_1$. Otherwise, when $d>1$, we must have $a=d$ and, in this context, ${\mathrm{𝚒𝚝𝚎𝚖}}_i$ $(1\le i\le a)$ 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{𝐶𝐿𝐼𝑄𝑈𝐸}\mapsto \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$ $(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},$ $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2})$ (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{𝚜𝚊𝚖𝚎}$$(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2})$ 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{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}\mapsto \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2})$ (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{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}\mapsto \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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ $(\mathrm{𝚂𝙸𝚉𝙴},$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})$ 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{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}\mapsto \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$ $(n>1)$ expressions then these expressions have the form:

  $\mathrm{𝐴𝑅𝐶}\_{\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}}_1\mapsto \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}({\mathrm{𝚒𝚝𝚎𝚖}}_1,{\mathrm{𝚒𝚝𝚎𝚖}}_2,\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_a)$

  $\mathrm{𝐴𝑅𝐶}\_{\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}}_2\mapsto \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}({\mathrm{𝚒𝚝𝚎𝚖}}_1,{\mathrm{𝚒𝚝𝚎𝚖}}_2,\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_a)$

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

  $\mathrm{𝐴𝑅𝐶}\_{\mathrm{𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅}}_n\mapsto \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}({\mathrm{𝚒𝚝𝚎𝚖}}_1,{\mathrm{𝚒𝚝𝚎𝚖}}_2,\cdots ,{\mathrm{𝚒𝚝𝚎𝚖}}_a)$

  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.