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 π™΅π™Ύπš 𝙰𝙻𝙻 π™Έπšƒπ™΄π™Όπš‚ 𝙾𝙡 iterator (e.g.,Β see for instance the definition of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint), which takes a collection C and generates an initial graph G i (t) 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 πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš 1 (X 1 ,X 2 ,...,X n ) and πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš 2 (X 1 ,X 2 ,...,X n ) are incompatible if there does not exist any tuple of values 〈v 1 ,v 2 ,...,v n βŒͺ such that both πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš 1 (X 1 ,X 2 ,...,X n ) and πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš 2 (X 1 ,X 2 ,...,X n ) hold.

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

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

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

    • 𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš– 1 ,πš’πšπšŽπš– 2 ,...,πš’πšπšŽπš– a ), where 𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 is one of the arc generators with a fixed arityAny arc generator different from 𝑃𝐴𝑇𝐻_1 and 𝑃𝐴𝑇𝐻_𝑁. defined in SectionΒ 2.2.2.3 on page 2.2.2.3, and πš’πšπšŽπš– i (1≀i≀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.2.2.2.1. which can be used within an arc constraint. When the Arc input(s) slot consists of one single collection (d=1), πš’πšπšŽπš– i (1≀i≀a) represents an item of the collection C 1 . Otherwise, when d>1, we must have a=d and, in this context, πš’πšπšŽπš– i (1≀i≀a) represents an item of C i .

      EXAMPLE: The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint has the following Arc input(s) and Arc generator slots:

      • Its Arc input(s) slot refers only to the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ (i.e.,Β d=1).

      • Its Arc generator slot consists of

        πΆπΏπΌπ‘„π‘ˆπΈ ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš— (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1, πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2) (i.e.,Β a=2).

      In this context, where d=1, both πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 are items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

      EXAMPLE: The πšœπšŠπš–πšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) constraint has the following Arc input(s) and Arc generator slots:

      • Its Arc input(s) slot refers to the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 (i.e.,Β d=2).

      • Its Arc generator slot consists of

        π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2) (i.e.,Β a=2).

      In this context, where d>1, πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 respectively correspond to items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections.

    • 𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—, where 𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 is one of the arc generators 𝑃𝐴𝑇𝐻_1 or 𝑃𝐴𝑇𝐻_𝑁. In this context, πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš— 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 πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš (πš‚π™Έπš‰π™΄, πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint has the following Arc input(s) and Arc generator slots:

      • Its Arc input(s) slot refers to the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

      • Its Arc generator slot consists of π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—.

      In this context, πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš— is a collection of the same type as the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ 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:

    𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 1 ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš– 1 ,πš’πšπšŽπš– 2 ,...,πš’πšπšŽπš– a )

    𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 2 ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš– 1 ,πš’πšπšŽπš– 2 ,...,πš’πšπšŽπš– a )

    ...............................................................

    𝐴𝑅𝐢_𝐺𝐸𝑁𝐸𝑅𝐴𝑇𝑂𝑅 n ↦ πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš– 1 ,πš’πšπšŽπš– 2 ,...,πš’πšπšŽπš– a )

    All leftmost part of the expressions must be the same since they will be involved in one single Arc constraint(s) slot. The πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ 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 πš’πš—πš, 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 𝑃𝐴𝑇𝐻_1 or 𝑃𝐴𝑇𝐻_𝑁 as in the πšŠπš›πš’πšπš‘_πšœπš•πš’πšπš’πš—πš or the πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš 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 πš—πšŸπšŠπš•πšžπšŽ 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 πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) restricts π™½πš…π™°π™» to be the number of distinct values taken by the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Its meaning is described by a simple graph constraint corresponding to the following items:

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

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generatorΒ Β Β Β Β Β :

πΆπΏπΌπ‘„π‘ˆπΈ β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

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

2

Arc constraint(s)Β Β Β :

πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›

Graph property(ies):

𝐍𝐒𝐂𝐂=π™½πš…π™°π™»

Since this description does not use the π™΅π™Ύπš 𝙰𝙻𝙻 π™Έπšƒπ™΄π™Όπš‚ 𝙾𝙡 iterator we generate one single initial graph. Each vertex of this graph corresponds to one item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. Since we use the πΆπΏπΌπ‘„π‘ˆπΈ 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 π™½πš…π™°π™» strongly connected components.

EXAMPLE: The constraint πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) forces all variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ 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)Β Β Β Β Β Β Β Β :

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generatorΒ Β Β Β Β Β :

𝑃𝐴𝑇𝐻 β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

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

𝐿𝑂𝑂𝑃 β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

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

2

Arc constraint(s)Β Β Β :

πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›

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

πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=1

Graph property(ies):

𝐍𝐂𝐂≀1

Since this description does not use the π™΅π™Ύπš 𝙰𝙻𝙻 π™Έπšƒπ™΄π™Όπš‚ 𝙾𝙡 iterator we generate one single initial graph. Each vertex of this graph corresponds to one item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. Since we use the 𝑃𝐴𝑇𝐻 arc generator we generate an arc from item πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i] to item πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i+1] (1≀i<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|). In addition, since we use the 𝐿𝑂𝑂𝑃 arc generator, we generate also an arc from each item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to itself.We use the 𝐿𝑂𝑂𝑃 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 𝐍𝐂𝐂≀1 enforces to have at most one such group of adjacent variables assigned to 1.

EXAMPLE:

The πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚) constraint enforces that each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• (1≀i≀|πš…π™°π™»πš„π™΄πš‚|) be taken by exactly πš…π™°π™»πš„π™΄πš‚[i].πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. Its meaning is described by a simple graph constraint corresponding to the following items:

For all items of πš…π™°π™»πš„π™΄πš‚:
Arc input(s)Β Β Β Β Β Β Β Β :

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generatorΒ Β Β Β Β Β :

𝑆𝐸𝐿𝐹 β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

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

1

Arc constraint(s)Β Β Β :

πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•

Graph property(ies):

𝐍𝐕𝐄𝐑𝐓𝐄𝐗=πš…π™°π™»πš„π™΄πš‚.πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ

Since this description uses the For all items of πš…π™°π™»πš„π™΄πš‚ iterator on the πš…π™°π™»πš„π™΄πš‚ collection we generate an initial graph for each item of the πš…π™°π™»πš„π™΄πš‚ collection (i.e.,Β one graph for each value). Each vertex of an initial graph corresponds to one item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. Since we use the 𝑆𝐸𝐿𝐹 arc generator we have an arc for each vertex. For an initial graph associated with a value π‘£π‘Žπ‘™ an arc constraint on a vertex v corresponds to an equality constraint between the variable associated with v and the value π‘£π‘Žπ‘™. Finally, the Graph property(ies) slot forces the final graph to have a given number of vertices (i.e.,Β associated with the attribute π‘£π‘Žπ‘™).