2.2.2.4. Graph properties

We represent a global constraint as the search of a subgraph (i.e.,Β a final graph) of a known initial graph, so that this final graph satisfies a given set of graph properties and eventually belongs to a specific graph class. Most graph properties have the form π™ΏπšŠπš›πšŠπš–πšŽπšπšŽπš› π™²πš˜πš–πš™πšŠπš›πš’πšœπš˜πš— π™΄πš‘πš™ or the form π™ΏπšŠπš›πšŠπš–πšŽπšπšŽπš› βˆ‰ [π™΄πš‘πš™ 1 ,π™΄πš‘πš™ 2 ], where π™ΏπšŠπš›πšŠπš–πšŽπšπšŽπš› is a graph parameterΒ [Berge70],Β [GondranMinoux84], π™²πš˜πš–πš™πšŠπš›πš’πšœπš˜πš— is one of the comparison operators =, <, β‰₯, >, ≀, β‰ , and π™΄πš‘πš™, π™΄πš‘πš™ 1 , π™΄πš‘πš™ 2 are expressions that can be evaluated to an integer. Before defining each graph parameter, let's first introduce some basic vocabulary on graphs.

Graph terminology and notations

A digraph G=(V(G),E(G)) is a pair where V(G) is a finite set, called the set of vertices, and where E(G) is a set of ordered pairs of vertices, called the set of arcs. The arc, path, circuit and strongly connected component of a graph G correspond to oriented concepts, while the edge, chain, cycle and connected component are non -oriented concepts. However, as reported inΒ [Berge70] an undirected graph can be seen as a digraph where to each edge we associate the corresponding two arcs. Parts (A) and (B) of FigureΒ 2.2.5 respectively illustrate the terms for undirected graphs and digraphs.

Figure 2.2.5. Graph terminology for an undirected graph and a digraph
ctrs/graph_terminology
  • We say that e 2 is a successor of e 1 if there exists an arc that starts from e 1 and ends at e 2 . In the same way, we say that e 2 is a predecessor of e 1 if there exists an arc that starts from e 2 and ends at e 1 .

  • A vertex of G that does not have any predecessor is called a source. A vertex of G that does not have any successor is called a sink.

  • A sequence (e 1 ,e 2 ,...,e k ) of edges of G such that each edge has a common vertex with the previous edge, and the other vertex common to the next edge is called a chain of length k. A chain where all vertices are distinct is called an elementary chain. Each equivalence class of the relation β€œe i is equal to e j or there exists a chain between e i and e j ” is a connected component of the graph G.

  • A sequence (e 1 ,e 2 ,...,e k ) of arcs of G such that, for each arc e i (1≀i<k) the end of e i is equal to the start of the arc e i+1 , is called a path of length k. A path where all vertices are distinct is called an elementary path. Each equivalence class of the relation β€œe i is equal to e j or there exists a path between e i and e j ” is a strongly connected component of the graph G.

  • A chain (e 1 ,e 2 ,...,e k ) of G is called a cycle if the same edge does not occur more than once in the chain and if the two extremities of the chain coincide. A cycle (e 1 ,e 2 ,...,e k ) of G is called a circuit if for each edge e i (1≀i<k), the end of e i is equal to the start of the edge e i+1 .

  • Given a graph G, we define the reduced graph R(G) of G as follows: to each strongly connected component of G corresponds a vertex of R(G); to each arc of G that connects different strongly connected components corresponds an arc in R(G) (multiple arcs between the same pair of vertices are merged).

  • The rank function associated with the vertices V(G) of a graph G that does not contain any circuit is defined in the following way:

    • The rank of the vertices that do not have any predecessor (i.e.,Β the sources) is equal to 0,

    • The rank r of a vertex v that is not a source is the length of longest path (e 1 , e 2 , ..., e r ) such that the start of the arc e 1 is a source and the end of arc e r is the vertex v.

We now present the different notations used in the catalogue:

  • [k] corresponds to {1,β‹―,k} for k any positive integer.

  • Given a set X, |X| is the number of its elements.

  • Given two sets X and Y, X⊎Y denotes the union of the two sets when they are disjoint.

  • Given a digraph G and x∈V(G), d G + (x)=|{y:y∈V(G):(x,y)∈E(G)}| and d G - (x)=|{y:y∈V(G):(y,x)∈E(G)}|.

  • Given a digraph G and X a subset of V(G), the subdigraph of G induced by X is the digraph G[X] where V(G[X])=X and E(G[X])=X 2 ∩E(G). By aim of simplicity, we denote G[V(G)-X] by G-X. Moreover, if X={x}, we use G-x instead of G-{x}.

  • Given two digraph G 1 and G 2 such that V(G 1 )∩V(G 2 )=βˆ…, G 1 βŠ•G 2 denotes the graph whose vertices set is V(G 1 )βˆͺV(G 2 ) and whose arcs set is E(G 1 )βˆͺE(G 2 ).

  • Given a graph parameter 𝐏∈{𝐍𝐂𝐂,𝐍𝐒𝐂𝐂}, a digraph G and an integer k, 𝐂𝐇(G,k) is the number of connected components (respectively strongly connected components) of G with cardinal k.

Given a graph parameter, for instance the number of connected components, 𝐍𝐂𝐂 π™Έπ™½π™Έπšƒπ™Έπ™°π™» will denote the number of connected components of the initial graph (i.e.,Β the graph induced by the constraint under consideration), 𝐍𝐂𝐂 will denote the number of connected components of the final graph (i.e.,Β a subgraph of the initial graph). The use of 𝐍𝐂𝐂(G) will denote the number of connected components of the digraph G.

Given a global constraint C, and a graph parameter 𝐏 used in the description of C, 𝐏 ̲ (respectively 𝐏 ¯) denotes a lower bound (respectively upper bound) of 𝐏 among all possible final graphs compatible with the current status of C.

Graph parameters

We list in alphabetic order the different graph parameters we consider for a final graph G f =(V(G f ),E(G f )) associated with a global constraint and give an example of constraint where they are used:

  • πŒπ€π—_𝐃𝐑𝐆 : largest distance between sources and sinks in the reduced graph associated with G f (adjacent vertices are at a distance of 1).

    EXAMPLE: We do not provide any example since πŒπ€π—_𝐃𝐑𝐆 is currently not used.

  • πŒπ€π—_πˆπƒ : number of predecessors of the vertex of G f that has the maximum number of predecessors without counting an arc from a vertex to itself.

    EXAMPLE: The πšŒπš’πš›πšŒπšžπš’πš constraint uses the graph property πŒπ€π—_πˆπƒ=1 in order to force each vertex of the final graph to have at most one predecessor.

  • πŒπ€π—_𝐍𝐂𝐂 : number of vertices of the largest connected component of G f .

    EXAMPLE: The πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ(πš‚π™Έπš‰π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš) constraint uses the graph property πŒπ€π—_𝐍𝐂𝐂=πš‚π™Έπš‰π™΄ in order to catch in πš‚π™Έπš‰π™΄ the maximum number of consecutive variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection for which constraint π™²πšƒπš holds.

  • πŒπ€π—_𝐍𝐒𝐂𝐂 : number of vertices of the largest strongly connected component of G f .

    EXAMPLE: The πšπš›πšŽπšŽ constraint covers a digraph by a set of trees in such a way that each vertex belongs to a distinct tree. It uses the graph -property πŒπ€π—_𝐍𝐒𝐂𝐂 ≀ 1 in order to avoid to have any circuit involving more than one vertex.

  • πŒπ€π—_πŽπƒ : number of successors of the vertex of G f that has the maximum number of successors without counting an arc from a vertex to itself.

    EXAMPLE: The πšπš˜πšžπš› constraint enforces to cover a graph with a Hamiltonian cycle. It uses the graph -property πŒπ€π—_πŽπƒ=2 to enforce that each vertex of G f have at most twoSince the πšπš˜πšžπš› constraint uses the πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) arc generator the vertices of G f do not have any loop. successors.

  • 𝐌𝐈𝐍_𝐃𝐑𝐆 : smallest distance between sources and sinks in the reduced graph associated with G f (adjacent vertices are at a distance of 1).

    EXAMPLE: We do not provide any example since 𝐌𝐈𝐍_𝐃𝐑𝐆 is currently not used by any constraint.

  • 𝐌𝐈𝐍_πˆπƒ : number of predecessors of the vertex of G f that has the minimum number of predecessors without counting an arc from a vertex to itself.

    EXAMPLE: The πšπš˜πšžπš› constraint enforces to cover a graph with a Hamiltonian cycle. It uses the graph -property 𝐌𝐈𝐍_πˆπƒ=2 to enforce that each vertex of G f have at most twoSince the πšπš˜πšžπš› constraint uses the πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) arc generator the vertices of G f do not have any loop. predecessors.

  • 𝐌𝐈𝐍_𝐍𝐂𝐂 : number of vertices of the smallest connected component of G f .

    EXAMPLE: Within the πšπš›πš˜πšžπš™ constraint, each connected component of G f corresponds to a maximum sequence of consecutive variables that take their value in a given set of values. Therefore, the graph -property 𝐌𝐈𝐍_𝐍𝐂𝐂=𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ enforces that the smallest sequence of such variables consist of 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄ variables.

  • 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 : number of vertices of the smallest strongly connected component of G f .

    EXAMPLE: The πšŒπš’πš›πšŒπšžπš’πš(NODES) constraint enforces covering a digraph with one circuit visiting once all its vertices. The graph -property 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=|π™½π™Ύπ™³π™΄πš‚| enforces that the smallest strongly connected component of G f contain |π™½π™Ύπ™³π™΄πš‚| vertices. Since |π™½π™Ύπ™³π™΄πš‚| also corresponds to the number of vertices of the initial graph this means that G f is a strongly connected component involving all the vertices. This is clearly a necessary conditionOf course, this is not enough, and the description of the πšŒπš’πš›πšŒπšžπš’πš constraint asks for some other properties. for having a circuit visiting once all vertices.

  • 𝐌𝐈𝐍_πŽπƒ : number of successors of the vertex of G f that has the minimum number of successors without counting an arc from a vertex to itself.

    EXAMPLE: The πšπš˜πšžπš› constraint enforces to cover a graph with a Hamiltonian cycle. It uses the graph -property 𝐌𝐈𝐍_πŽπƒ=2 to enforce that each vertex of G f have at most twoSince the πšπš˜πšžπš› constraint uses the πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) arc generator the vertices of G f do not have any loop. successors.

  • 𝐍𝐀𝐑𝐂 : cardinality of the set E(G f ).

    EXAMPLE: The πšπš’πšœπš“πš˜πš’πš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) constraint enforces that each variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 take a value that is distinct from all the values assigned to the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

    This is imposed by creating an arc from each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 to each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2. To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. Finally, the graph property 𝐍𝐀𝐑𝐂=0 forces G f to be empty so that no value is both assigned to a variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 as well as to a variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

  • 𝐍𝐀𝐑𝐂_𝐍𝐎_π‹πŽπŽπ : cardinality of the set E(G f ) without considering the arcs linking the same vertex (i.e.,Β a loop).

  • 𝐍𝐂𝐂 : number of connected components of G f .

    EXAMPLE: The πšπš›πšŽπšŽ constraint covers a digraph by π™½πšƒπšπ™΄π™΄πš‚ trees in such a way that each vertex belongs to a distinct tree. It uses the graph -property 𝐍𝐂𝐂=π™½πšƒπšπ™΄π™΄πš‚ in order to state that G f is made up from π™½πšƒπšπ™΄π™΄πš‚ connected components.

  • 𝐍𝐒𝐂𝐂 : number of strongly connected components of G f .

    EXAMPLE: The constraint πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) forces π™½πš…π™°π™» to be equal to the number of distinct values assigned to the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. This is enforced by using the graph -property 𝐍𝐒𝐂𝐂=π™½πš…π™°π™». Each strongly connected component of the final graph corresponds to the variables that are assigned to the same value.

  • ππ’πˆππŠ : number of vertices of G f that do not have any successor.

    EXAMPLE: The πšœπšŠπš–πšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) enforces that the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 collection correspond to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collection according to a permutation.

    We first create an arc from each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 to each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2. To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. We use the graph -property ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| in order to express the fact that each value assigned to a variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 should also be assigned to a variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.

  • ππ’πˆππŠ_ππ’πŽπ”π‘π‚π„ : sum over the different connected components of G f of the minimum of the number of sinks and the number of sources of a connected component.

    EXAMPLE: The 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πšŸπšŠπš›(𝙲,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) constraint enforces 𝙲 to be the minimum number of values to change in the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections of variablesBoth collections have the same number of variables., so that the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 correspond to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 according to a permutation.

    A connected component π’ž π‘£π‘Žπ‘™ of the final graph G f corresponds to all variables that are assigned to the same value π‘£π‘Žπ‘™: the sources and the sinks of π’ž π‘£π‘Žπ‘™ respectively correspond to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 that are assigned to π‘£π‘Žπ‘™. For a connected component, the minimum of the number of sources and sinks expresses the number of variables for which we do not need to make any change. Therefore we use the graph -property ππ’πˆππŠ_ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|-𝙲 for encoding the meaning of the 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πšŸπšŠπš› constraint.

  • ππ’πŽπ”π‘π‚π„ : number of vertices of G f that do not have any predecessor.

    EXAMPLE: The πšœπšŠπš–πšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) enforces that the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 collection correspond to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collection according to a permutation.

    We first create an arc from each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 to each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2. To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. We use the graph -property ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| in order to express the fact that each value assigned to a variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 should also be assigned to a variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

  • 𝐍𝐓𝐑𝐄𝐄 : number of vertices of G f that do not belong to any circuit and for which at least one successor belongs to a circuit. Such vertices can be interpreted as root nodes of a tree.

    EXAMPLE: The πšŒπš’πšŒπš•πšŽ(π™½π™²πšˆπ™²π™»π™΄,π™½π™Ύπ™³π™΄πš‚) enforces that π™½π™²πšˆπ™²π™»π™΄ equal the number of circuits for covering an initial graph in such a way that each vertex belongs to one single circuit.

    The graph -property 𝐍𝐓𝐑𝐄𝐄=0 enforces that all vertices of the final graph belong to a circuit.

  • 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 : cardinality of the set V(G f ).

    EXAMPLE: The 𝚌𝚞𝚝𝚜𝚎𝚝(πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ,π™½π™Ύπ™³π™΄πš‚) constraint considers a digraph with n vertices described by the π™½π™Ύπ™³π™΄πš‚ collection. It enforces that the subset of kept vertices of cardinality n-πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ and their corresponding arcs form a graph without a circuit. It uses the graph -property 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=n-πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ for enforcing that the final graph G f contain the required number of vertices.

  • 𝐑𝐀𝐍𝐆𝐄_𝐃𝐑𝐆 : difference between the largest distance between sources and sinks in the reduced graph associated with G f and the smallest distance between sources and sinks in the reduced graph associated with G f .

    EXAMPLE: The πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽ constraint enforces to cover a digraph in such a way that each vertex belongs to a distinct tree. In addition it forces the difference between the longest and the shortest paths of G f to be equal to the variable 𝚁. For this purpose it uses the graph -property 𝐑𝐀𝐍𝐆𝐄_𝐃𝐑𝐆=𝚁.

  • 𝐑𝐀𝐍𝐆𝐄_𝐍𝐂𝐂 : difference between the number of vertices of the largest connected component of G f and the number of vertices of the smallest connected component of G f .

    EXAMPLE: We do not provide any example since 𝐑𝐀𝐍𝐆𝐄_𝐍𝐂𝐂 is currently not used by any constraint.

  • 𝐑𝐀𝐍𝐆𝐄_𝐍𝐒𝐂𝐂 : difference between the number of vertices of the largest strongly connected component of G f and the number of vertices of the smallest strongly connected component of G f .

    EXAMPLE: The πš‹πšŠπš•πšŠπš—πšŒπšŽ(𝙱𝙰𝙻𝙰𝙽𝙲𝙴,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint forces 𝙱𝙰𝙻𝙰𝙽𝙲𝙴 to be equal to the difference between the number of occurrences of the value that occurs the most and the value that occurs the least within the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Each strongly connected component of G f corresponds to the variables that are assigned to the same value. The graph property 𝐑𝐀𝐍𝐆𝐄_𝐍𝐒𝐂𝐂=𝙱𝙰𝙻𝙰𝙽𝙲𝙴 allows for expressing this definition.

  • πŽπ‘πƒπ„π‘(πš›πšŠπš—πš”,πšπšŽπšπšŠπšžπš•πš,πšŠπšπšπš›)

    • πš›πšŠπš—πš” is an integer or an argument of type integer of the global constraint,

    • πšπšŽπšπšŠπšžπš•πš is an integer,

    • πšŠπšπšπš› is an attribute corresponding to an integer or to a domain variable that occurs in all the collections that were used for generating the vertices of the initial graph.

    We explain what is the value associated with πŽπ‘πƒπ„π‘(πš›πšŠπš—πš”,πšπšŽπšπšŠπšžπš•πš,πšŠπšπšπš›). Let 𝒱 denote the vertices of rank πš›πšŠπš—πš” of G f from which we remove any loops.

    • When 𝒱 is not empty, it corresponds to the values of attribute πšŠπšπšπš› of the items associated with the vertices of 𝒱,

    • Otherwise, when 𝒱 is empty, it corresponds to the default value πšπšŽπšπšŠπšžπš•πš.

    EXAMPLE: The πš–πš’πš—πš’πš–πšžπš–(𝙼𝙸𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) forces 𝙼𝙸𝙽 to be the minimum value of the collection of domain variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. There is an arc from a variable πšŸπšŠπš› 1 to a variable πšŸπšŠπš› 2 if and only if πšŸπšŠπš› 1 <πšŸπšŠπš› 2 . The graph -property πŽπ‘πƒπ„π‘(0,π™Όπ™°πš‡π™Έπ™½πšƒ,πšŸπšŠπš›)=𝙼𝙸𝙽 expresses the fact that 𝙼𝙸𝙽 is equal to the value of the source of G f (since πš›πšŠπš—πš”=0).

  • 𝐏𝐀𝐓𝐇_π…π‘πŽπŒ_π“πŽ(πšŠπšπšπš›,πšπš›πš˜πš–,𝚝𝚘)

      • πšŠπšπšπš› is an attribute corresponding to an integer that occurs in all the collections that were used for generating the vertices of the initial graph,

      • πšπš›πš˜πš– is an integer or an argument of type integer of the global constraint,

      • 𝚝𝚘 is an integer or an argument of type integer of the global constraint.

      Let β„± (respectively 𝒯) denote the vertices of G f such that πšŠπšπšπš› is equal to πšπš›πš˜πš– (respectively 𝚝𝚘). 𝐏𝐀𝐓𝐇_π…π‘πŽπŒ_π“πŽ(πšŠπšπšπš›,πšπš›πš˜πš–,𝚝𝚘) is equal to 1 if there exists a path between each vertex of β„± and each vertex of 𝒯, and 0 if there exists no path between a vertex of β„± and a vertex of 𝒯.

      • πšŠπšπšπš› is an attribute corresponding to an integer that occurs in all the collections that were used for generating the vertices of the initial graph,

      • πšπš›πš˜πš– is an attribute corresponding to an integer or to a set of integers that occurs in all the collections that were used for generating the vertices of the initial graph,

      • 𝚝𝚘 is an attribute corresponding to an integer or to a set of integers that occurs in all the collections that were used for generating the vertices of the initial graph,

      For each vertex v of G f let:

      • β„± v the set of vertices for which the value of the attribute πšŠπšπšπš› is equal to the πšπš›πš˜πš– attribute (or is included within the πšπš›πš˜πš– attribute when it corresponds to a set of integers).

      • 𝒯 v the set of vertices for which the value of the attribute πšŠπšπšπš› is equal to the 𝚝𝚘 attribute (or is included within the 𝚝𝚘 attribute when it corresponds to a set of integers).

      𝐏𝐀𝐓𝐇_π…π‘πŽπŒ_π“πŽ(πšŠπšπšπš›,πšπš›πš˜πš–,𝚝𝚘) is equal to

      • 1 if for each vertex of G f there exists a path between each vertex of β„± v and each vertex of 𝒯 v .

      • 0 if for a vertex of G f there is no path between a vertex of β„± v and a vertex of 𝒯 v .

  • ππ‘πŽπƒ(πšŒπš˜πš•,πšŠπšπšπš›)

    • πšŒπš˜πš• is a collection that was used for generating the vertices of the initial graph,

    • πšŠπšπšπš› is an attribute corresponding to an integer or to a domain variable of the collection πšŒπš˜πš•.

    Let 𝒱 be the set of vertices of G f that were generated from the items of the collection πšŒπš˜πš•.

    • If 𝒱 is not empty, ππ‘πŽπƒ(πšŒπš˜πš•,πšŠπšπšπš›) corresponds to the product of the values of attribute πšŠπšπšπš› associated with the vertices of 𝒱,

    • Otherwise, if 𝒱 is empty, ππ‘πŽπƒ(πšŒπš˜πš•,πšŠπšπšπš›) is equal to 1.

    EXAMPLE: The constraint πš™πš›πš˜πšπšžπšŒπš_πšŒπšπš›(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš,πš…π™°πš) forces the product of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to be equal, less than or equal, ... to a given domain variable πš…π™°πš.

    To each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the 𝑆𝐸𝐿𝐹 arc generator together with the πšƒπšπš„π™΄ arc constraint. Finally, ππ‘πŽπƒ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›) π™²πšƒπš πš…π™°πš expresses the required condition. In this expression πšŸπšŠπš› and π™²πšƒπš respectively corresponds to the attribute of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ (a domain variable) and to the condition we want to enforce. Since the final graph G f contains all the vertices of the initial graph, the expression ππ‘πŽπƒ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›) corresponds to the product of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

  • 𝐑𝐀𝐍𝐆𝐄(πšŒπš˜πš•,πšŠπšπšπš›)

    • πšŒπš˜πš• is a collection that was used for generating the vertices of the initial graph,

    • πšŠπšπšπš› is an attribute corresponding to an integer or to a domain variable of the collection πšŒπš˜πš•.

    Let 𝒱 be the set of vertices of G f that were generated from the items of the collection πšŒπš˜πš•.

    • If 𝒱 is not empty, 𝐑𝐀𝐍𝐆𝐄(πšŒπš˜πš•,πšŠπšπšπš›) corresponds to the difference between the maximum and the minimum values of attribute πšŠπšπšπš› associated with the vertices of 𝒱,

    • Otherwise, if 𝒱 is empty, 𝐑𝐀𝐍𝐆𝐄(πšŒπš˜πš•,πšŠπšπšπš›) is equal to 0.

    EXAMPLE: The constraint πš›πšŠπš—πšπšŽ_πšŒπšπš›(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš,πš…π™°πš) forces the difference between the maximum value and the minimum value of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to be equal, less than or equal, ... to a given domain variable πš…π™°πš.

    To each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the 𝑆𝐸𝐿𝐹 arc generator together with the πšƒπšπš„π™΄ arc constraint. Finally, 𝐑𝐀𝐍𝐆𝐄(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›) π™²πšƒπš πš…π™°πš expresses the required condition. In this expression πšŸπšŠπš› and π™²πšƒπš respectively corresponds to the attribute of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ (a domain variable) and to the condition we want to enforce. Since the final graph G f contains all the vertices of the initial graph, the expression 𝐑𝐀𝐍𝐆𝐄(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›) corresponds to the difference between the maximum value and the minimum value of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

  • π’π”πŒ(πšŒπš˜πš•,πšŠπšπšπš›)

    • πšŒπš˜πš• is a collection that was used for generating the vertices of the initial graph,

    • πšŠπšπšπš› is an attribute corresponding to an integer or to a domain variable of the collection πšŒπš˜πš•.

    Let 𝒱 be the set of vertices of G f that were generated from the items of the collection πšŒπš˜πš•.

    • If 𝒱 is not empty, π’π”πŒ(πšŒπš˜πš•,πšŠπšπšπš›) corresponds to the sum of the values of attribute πšŠπšπšπš› associated with the vertices of 𝒱,

    • Otherwise, if 𝒱 is empty, π’π”πŒ(πšŒπš˜πš•,πšŠπšπšπš›) is equal to 0.

    EXAMPLE: The constraint πšœπšžπš–_πšŒπšπš›(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš,πš…π™°πš) forces the sum of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to be equal, less than or equal, ... to a given domain variable πš…π™°πš.

    To each variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the 𝑆𝐸𝐿𝐹 arc generator together with the πšƒπšπš„π™΄ arc constraint. Finally, π’π”πŒ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›) π™²πšƒπš πš…π™°πš expresses the required condition. In this expression πšŸπšŠπš› and π™²πšƒπš respectively correspond to the attribute of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ (a domain variable) and to the condition we want to enforce. Since the final graph G f contains all the vertices of the initial graph, the expression π’π”πŒ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›) corresponds to the sum of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

  • π’π”πŒ_π–π„πˆπ†π‡π“_𝐀𝐑𝐂(π™΄πš‘πš™πš›) π™΄πš‘πš™πš› is an arithmetic expression. For each arc a of E(G f ), let f(a) denote the value of π™΄πš‘πš™πš›. π’π”πŒ_π–π„πˆπ†π‡π“_𝐀𝐑𝐂(π™΄πš‘πš™πš›) is equal to βˆ‘ a∈E(G f ) f(a). The value of π™΄πš‘πš™πš› usually depends on the attributes of the items located at the extremities of an arc.

    EXAMPLE: The constraint πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, πš…π™°π™»πš„π™΄πš‚,π™Όπ™°πšƒπšπ™Έπš‡,π™²π™Ύπš‚πšƒ) enforces that each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• be assigned to exactly πš…π™°π™»πš„π™΄πš‚[i].πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. In addition the π™²π™Ύπš‚πšƒ of an assignment is equal to the sum of the elementary costs associated with the fact that we assign the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to the j th value of the πš…π™°π™»πš„π™΄πš‚ collection. These elementary costs are given by the π™Όπ™°πšƒπšπ™Έπš‡ collection.

    The graph -property πš‚πš„π™Ό_πš†π™΄π™Έπ™Άπ™·πšƒ_π™°πšπ™²(π™Όπ™°πšƒπšπ™Έπš‡[(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’-1)*πšœπš’πš£πšŽ(πš…π™°π™»πš„π™΄πš‚)+πšŸπšŠπš•πšžπšŽπšœ.πš”πšŽπš’].𝚌)=π™²π™Ύπš‚πšƒ expresses the fact that the π™²π™Ύπš‚πšƒ variable is equal to the sum of the elementary costs associated with each variable -value assignment. All these elementary costs are recorded in the π™Όπ™°πšƒπšπ™Έπš‡ collection. More precisely, the cost c ij is recorded in the attribute 𝚌 of the ((i-1)*|πš…π™°π™»πš„π™΄πš‚)|+j) th entry of the π™Όπ™°πšƒπšπ™Έπš‡ collection.

A last graph parameter, πƒπˆπ’π“π€ππ‚π„ , is computed on two final graphs G 1 and G 2 that have the same set V of vertices and the sets E(G 1 ) and E(G 2 ) of arcs. This graph parameter is the cardinality of the set (E(G 1 )-E(G 2 ))βˆͺ(E(G 2 )-E(G 1 )). This corresponds to the number of arcs that belong to E(G 1 ) but not to E(G 2 ), plus the number of arcs that are in E(G 2 ) but not in E(G 1 ).

Graph class

For a given global constraint, a graph class specifies a general property that holds on its final digraph. We list the different graph classes and, for each of them, we point to some global constraints that fit in that class. Finding all the global constraints corresponding to a given graph class can be done by looking into the list of keywords (see SectionΒ 3.7 on page 3.7).

  • π™°π™²πšˆπ™²π™»π™Έπ™² : the final graph doesn't have any circuit.

  • π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄ : the final graph is bipartite.

  • π™²π™Ύπ™½πš‚π™΄π™²πš„πšƒπ™Έπš…π™΄_π™»π™Ύπ™Ύπ™Ώπš‚_π™°πšπ™΄_π™²π™Ύπ™½π™½π™΄π™²πšƒπ™΄π™³ : denotes the fact that the graph constraint of a global constraint uses only the 𝑃𝐴𝑇𝐻 and the 𝐿𝑂𝑂𝑃 arc generators and that the final graph does not contain consecutive vertices that have a loop and that are not connected together by an arc.

  • π™΄πš€πš„π™Έπš…π™°π™»π™΄π™½π™²π™΄ : the final graph is reflexive, symmetric and transitive.

  • 𝙽𝙾_𝙻𝙾𝙾𝙿 : the final graph doesn't have any loop.

  • 𝙾𝙽𝙴_πš‚πš„π™²π™² : the vertices of the initial graph belong to the final graph and all vertices of the final graph have exactly one successor.

  • πš‚πšˆπ™Όπ™Όπ™΄πšƒπšπ™Έπ™² : the final graph is symmetric. A digraph is symmetric if and only if, if there is an arc from a vertex u to a vertex v, there is also an arc from v to u.