2.2.2.3. Graph generators

This section describes how to generate the initial graph associated with a global constraint. Initial graphs correspond to directed hypergraphs [Berge87], which have a very regular structure. They are defined in the following way:

  • The vertices of the directed hypergraph are generated from collections of items such that each item corresponds to one vertex of the directed hypergraph. These collections are either collections that arise as arguments of the global constraint, or collections that are derived from one or several arguments of the global constraint. In this latter case these derived collections are computed by using the collection generators previously introduced (see Section 2.2.2.1 on page 2.2.2.1).

  • To all arcs of the directed hypergraph corresponds the same arc constraint that involves vertices in a given order.Usually the edges of a hypergraph are not oriented [Berge87]. However for our purpose we need to define an order on the vertices of an edge since the corresponding arc constraint takes its arguments in a given order. These arc constraints, which are mainly unary and binary constraints, were described in the previous section (see Section 2.2.2.2 on page 2.2.2.2). We describe all the arcs of an initial graph with a set of predefined arc generators, which correspond to classical regular structures one can find in the graph literature [Skiena90]. An arc generator of arity a takes n collections of items, denoted 𝚌 i (1in), as input and returns the corresponding hypergraph where the vertices are the items of the input collections 𝚌 i (1in) and where all arcs involve a vertices. Specific arc generators allow for giving an a -ary constraint for which a is not fixed, which means that the corresponding hypergraph contains arcs involving various number of vertices.

Each arc generator has a name and takes one or several collections of items as input and generates a set of arcs. Each arc is made from a sequence of items i 1 i 2 ... i a and is denoted by (i 1 ,i 2 ,...,i a ). a is called the arity of the arc generator. We have the following types of arc generators:

  • Arc generators with a fixed predefined arity. In fact most arc generators have a fixed predefined arity of 2. The graphs they generate correspond to digraphs.

  • Arc generators that can be used with any arity a greater than or equal to 1. These arc generators generate directed hypergraphs where all arcs consist of a items.

  • Arc generators that generate arcs that do not involve the same number of items.

We now give the list of arc generators, listed in alphabetic order, and the arcs they generate. For each arc generator we point to a global constraint where it is used in practice. Finally, Figure 2.2.4 illustrates the different arc generators. At present the following arc generators are in use:

  • 𝐶𝐻𝐴𝐼𝑁 has a predefined arity of 2. It takes one collection 𝚌 and generates the following arcsAs defined in Section 2.1.2 on page 2.1.2 we use the following notation: for a given collection 𝚌, |𝚌| and 𝚌[i] respectively denote the number of items of 𝚌 and the i th item of 𝚌.:

    • i[1,|𝚌|-1]: (𝚌[i],𝚌[i+1]),

    • i[1,|𝚌|-1]: (𝚌[i+1],𝚌[i]).

  • 𝐶𝐼𝑅𝐶𝑈𝐼𝑇 has a predefined arity of 2. It takes one collection 𝚌 and generates the following arcs:

    • i[1,|𝚌|-1]: (𝚌[i],𝚌[i+1]),

    • (𝚌[|𝚌|],𝚌[1]).

    EXAMPLE: The arc generator 𝐶𝐼𝑅𝐶𝑈𝐼𝑇 is for instance used in the 𝚌𝚒𝚛𝚌𝚞𝚕𝚊𝚛_𝚌𝚑𝚊𝚗𝚐𝚎 constraint.

  • 𝐶𝐿𝐼𝑄𝑈𝐸 can be used with any arity a greater than or equal to 2. It takes one collection 𝚌 and generates the arcs: i 1 [1,|𝚌|],i 2 [1,|𝚌|],...,i a [1,|𝚌|]:(𝚌[i 1 ],𝚌[i 2 ],...,𝚌[i a ]).

    EXAMPLE: The arc generator 𝐶𝐿𝐼𝑄𝑈𝐸 is usually used with an arity a=2. This is for instance the case of the 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint.

  • 𝐶𝐿𝐼𝑄𝑈𝐸(𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗), where 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 is one of the comparison operators , , <, >, =, , can be used with any arity a greater than or equal to 2. It takes one collection 𝚌 and generates the arcs:

    i 1 [1,|𝚌|],

    i 2 [1,|𝚌|] such that i 1 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 i 2 ,

    .......................................,

    i a [1,|𝚌|] such that i a-1 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 i a :(𝚌[i 1 ],𝚌[i 2 ],...,𝚌[i a ]).

    EXAMPLE: The 𝚘𝚛𝚌𝚑𝚊𝚛𝚍(𝚃𝚁𝙴𝙴𝚂) constraint is an example of constraint that uses the 𝐶𝐿𝐼𝑄𝑈𝐸(<) arc generator with an arity a=3. It generates an arc for each set of three trees.

  • 𝐶𝑌𝐶𝐿𝐸 has a predefined arity of 2. It takes one collection 𝚌 and generates the following arcs:

    • i[1,|𝚌|-1] (𝚌[i],𝚌[i+1]) and (𝚌[i+1],𝚌[i]),

    • (𝚌[|𝚌|],𝚌[1]) and (𝚌[1],𝚌[|𝚌|]).

    The arc generator 𝐶𝑌𝐶𝐿𝐸 is currently not used.

  • 𝐺𝑅𝐼𝐷([d 1 ,d 2 ,...,d n ]) takes a collection 𝚌 consisting of d 1 ·d 2 · ·d n items and generates the arcs (𝚌[i],𝚌[j]) where i and j satisfy the following condition. There exists an integer α (0αn-1) such that (1) and (2) hold:

    (1) |i-j|= 1kα d k (when α=0 we have 1kα =1),

    (2) i 1kα+1 d k =j 1kα+1 d k .

    EXAMPLE: The 𝚌𝚘𝚗𝚗𝚎𝚌𝚝_𝚙𝚘𝚒𝚗𝚝𝚜 constraint uses the 𝐺𝑅𝐼𝐷 arc generator.

  • 𝐿𝑂𝑂𝑃 has a predefined arity of 2. It takes one collection 𝚌 and generates the arcs: i[1,|𝚌|]: (𝚌[i],𝚌[i]). 𝐿𝑂𝑂𝑃 is usually used in order to generate a loop on some vertices, so that they do not disappear from the final graph.

    EXAMPLE: The 𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂) constraint is an example of constraint that uses the 𝐿𝑂𝑂𝑃 arc generator so that each variable of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 collection belongs to the final graph.

  • 𝑃𝐴𝑇𝐻 can be used with any arity a greater than or equal to 1. It takes one collection 𝚌, and generates the following arcs: i[1,|𝚌|-a+1]:(𝚌[i],𝚌[i+1],...,𝚌[i+a-1]).

    EXAMPLE: 𝑃𝐴𝑇𝐻 is for instance used in the 𝚜𝚕𝚒𝚍𝚒𝚗𝚐_𝚜𝚞𝚖(𝙻𝙾𝚆, 𝚄𝙿, 𝚂𝙴𝚀, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂) constraint with an arity 𝚂𝙴𝚀, where 𝚂𝙴𝚀 is an argument of the 𝚜𝚕𝚒𝚍𝚒𝚗𝚐_𝚜𝚞𝚖 constraint.

  • 𝑃𝐴𝑇𝐻_1 generates arcs that do not involve the same number of items. It takes one collection 𝚌, and generates the following arcs: (𝚌[1]), (𝚌[1],𝚌[2]), ... , (𝚌[1], 𝚌[2], ..., 𝚌[|𝚌|]).

  • 𝑃𝐴𝑇𝐻_𝑁 generates arcs that do not involve the same number of items. It takes one collection 𝚌, and generates the following arcs: i[1,|𝚌|],j[i,|𝚌|]: (𝚌[i], 𝚌[i+1], ..., 𝚌[j]).

  • 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 has a predefined arity of 2. It takes two collections 𝚌 1 , 𝚌 2 and generates the arcs: i[1,|𝚌 1 |],j[1,|𝚌 2 |]: (𝚌 1 [i],𝚌 2 [j]).

    EXAMPLE: 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 is for instance used in the 𝚜𝚊𝚖𝚎(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2) constraint for generating an arc from every item of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1 collection to every item of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2 collection.

  • 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗), where 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 is one of the comparison operators , , <, >, =, , has a predefined arity of 2. It takes two collections 𝚌 1 , 𝚌 2 and generates the arcs: i[1,|𝚌 1 |],j[1,|𝚌 2 |] such that i 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 j: (𝚌 1 [i],𝚌 2 [j]).

    EXAMPLE: 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(=) is for instance used in the 𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜(𝙺,𝚅𝙴𝙲𝚃𝙾𝚁1,𝚅𝙴𝙲𝚃𝙾𝚁2) constraint in order to generate an arc between the i th component of 𝚅𝙴𝙲𝚃𝙾𝚁1 and the i th component of 𝚅𝙴𝙲𝚃𝙾𝚁2.

  • 𝑆𝐸𝐿𝐹 has a predefined arity of 1. It takes one collection 𝚌 and generates the arcs: i[1,|𝚌|]: (𝚌[i]).

    EXAMPLE: 𝑆𝐸𝐿𝐹 is for instance used in the 𝚊𝚖𝚘𝚗𝚐(𝙽𝚅𝙰𝚁,𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂,𝚅𝙰𝙻𝚄𝙴𝚂) constraint in order to generate a unary arc constraint 𝚒𝚗(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜.𝚟𝚊𝚛,𝚅𝙰𝙻𝚄𝙴𝚂) for each variable of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 collection.

  • 𝑆𝑌𝑀𝑀𝐸𝑇𝑅𝐼𝐶_𝑃𝑅𝑂𝐷𝑈𝐶𝑇 has a predefined arity of 2. It takes two collections 𝚌 1 , 𝚌 2 and generates the following arcs: i[1,|𝚌 1 |],j[1,|𝚌 2 |]: (𝚌 1 [i],𝚌 2 [j]) and (𝚌 2 [j],𝚌 1 [i]).

  • 𝑆𝑌𝑀𝑀𝐸𝑇𝑅𝐼𝐶_𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗), where 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 is one of the comparison operators , , <, >, =, , has a predefined arity of 2. It takes two collections 𝚌 1 , 𝚌 2 and generates the arcs: i[1,|𝚌 1 |],j[1,|𝚌 2 |] such that i 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗 j: (𝚌 1 [i],𝚌 2 [j]) and (𝚌 2 [j],𝚌 1 [i]).

  • 𝑉𝑂𝐼𝐷 takes one collection and does not generate any arc.

    EXAMPLE: 𝑉𝑂𝐼𝐷 is for instance used in the 𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚 constraint.

Finally, we can combine the 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 arc generator with the arc generators from the following set 𝒢𝑒𝑛𝑒𝑟𝑎𝑡𝑜𝑟= {𝐶𝐼𝑅𝐶𝑈𝐼𝑇, 𝐶𝐻𝐴𝐼𝑁, 𝐶𝐿𝐼𝑄𝑈𝐸, 𝐿𝑂𝑂𝑃, 𝑃𝐴𝑇𝐻, 𝑉𝑂𝐼𝐷}. This is achieved by using the construction 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝙶 1 ,𝙶 2 ) where 𝙶 1 and 𝙶 2 belong to 𝒢𝑒𝑛𝑒𝑟𝑎𝑡𝑜𝑟. It applies 𝙶 1 to the first collection 𝚌 1 passed to 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 and 𝙶 2 to the second collection 𝚌 2 passed to 𝑃𝑅𝑂𝐷𝑈𝐶𝑇. Finally, it applies 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 on 𝚌 1 and 𝚌 2 . In a similar way the 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗) arc generator is extended to 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝙶 1 , 𝙶 2 , 𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗).

EXAMPLE: As an illustrative example, consider the 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚕𝚞𝚎(𝙽𝚂𝙰𝙼𝙴,𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1,𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2) constraint, which uses the arc generator 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝐶𝐿𝐼𝑄𝑈𝐸,𝐿𝑂𝑂𝑃,=) on the collections 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1 and 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2. It generates the following arcs:

  • Since the first argument of 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 is 𝐶𝐿𝐼𝑄𝑈𝐸 it generates an arc between each pair of items of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1 collection.

  • Since the second argument of 𝑃𝑅𝑂𝐷𝑈𝐶𝑇 is 𝐿𝑂𝑂𝑃 it generates a loop for each item of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2 collection.

  • Since the third argument is the comparison operator = it finally generates an arc between an item of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1 collection and an item of the 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2 collection when the two items have the same position.

Figure 2.2.3 shows the generated graph under the hypothesis that 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂1 and 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂2 have respectively 3 and 3 items.

Figure 2.2.3. Example of initial graph generated by 𝑃𝑅𝑂𝐷𝑈𝐶𝑇(𝐶𝐿𝐼𝑄𝑈𝐸,𝐿𝑂𝑂𝑃,=)
ctrs/product_clique_loop

Figure 2.2.4 illustrates the different arc generators. On the one hand, for those arc generators that take one single collection, we apply them on the collection of items i-1,i-2,i-3,i-4. On the other hand, for those arc generators that take two collections, we apply them on i-1,i-2 and i-3,i-4. We use the following pictogram for the graphical representation of a constraint network:

  • A line for an arc constraint of arity 1,

  • An arrow for an arc constraint of arity 2,

  • A closed line for an arc constraint with an arity strictly greater than 2. In this last case, since the vertices of an arc are ordered, a black circle at one of the extremities indicates the direction of the closed line. For instance consider the example of 𝑃𝐴𝑇𝐻_1 in Figure 2.2.4. The closed line that contains vertices 1, 2 and 3 means that a 3 -ary arc constraint involves items 1, 2, and 3 in this specific order.

Dotted circles represent vertices that do not belong to the graph. This stems from the fact that the arc generator did not produce any arc involving these vertices. The leftmost lowest corner indicates the arity of the corresponding arc generator:

  • An integer if it has a fixed predefined arity,

  • n if it can be used with any arity greater than or equal to 1,

  • * if it generates arcs that do not necessarily involve the same number of items.

Figure 2.2.4. Examples of arc generators
ctrs/arc_generator