### 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 $\mathrm{\pi Ώ\pi \pi \pi \pi \pi \pi \pi \pi }\mathrm{\pi ²\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathrm{\pi ΄\pi ‘\pi }$ or the form $\mathrm{\pi Ώ\pi \pi \pi \pi \pi \pi \pi \pi }\beta \left[{\mathrm{\pi ΄\pi ‘\pi }}_{1},{\mathrm{\pi ΄\pi ‘\pi }}_{2}\right]$, where $\mathrm{\pi Ώ\pi \pi \pi \pi \pi \pi \pi \pi }$ is a graph parameterΒ [Berge70],Β [GondranMinoux84], $\mathrm{\pi ²\pi \pi \pi \pi \pi \pi \pi \pi \pi }$ is one of the comparison operators $=$, $<$, $\beta ₯$, $>$, $\beta €$, , and $\mathrm{\pi ΄\pi ‘\pi }$, ${\mathrm{\pi ΄\pi ‘\pi }}_{1}$, ${\mathrm{\pi ΄\pi ‘\pi }}_{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=\left(V\left(G\right),E\left(G\right)\right)$ is a pair where $V\left(G\right)$ is a finite set, called the set of vertices, and where $E\left(G\right)$ 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.

• 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 $\left({e}_{1},{e}_{2},...,{e}_{k}\right)$ 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 $\left({e}_{1},{e}_{2},...,{e}_{k}\right)$ of arcs of $G$ such that, for each arc ${e}_{i}$ $\left(1\beta €i 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 $\left({e}_{1},{e}_{2},...,{e}_{k}\right)$ 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 $\left({e}_{1},{e}_{2},...,{e}_{k}\right)$ of $G$ is called a circuit if for each edge ${e}_{i}$ $\left(1\beta €i, 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\left(G\right)$ of $G$ as follows: to each strongly connected component of $G$ corresponds a vertex of $R\left(G\right)$; to each arc of $G$ that connects different strongly connected components corresponds an arc in $R\left(G\right)$ (multiple arcs between the same pair of vertices are merged).

• The rank function associated with the vertices $V\left(G\right)$ 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 $\left({e}_{1},$ ${e}_{2},$ $...,$ ${e}_{r}\right)$ 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:

• $\left[k\right]$ corresponds to $\left\{1,\beta ―,k\right\}$ for $k$ any positive integer.

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

• Given two sets $X$ and $Y$, $X\beta Y$ denotes the union of the two sets when they are disjoint.

• Given a digraph $G$ and $x\beta V\left(G\right)$, ${d}_{G}^{+}\left(x\right)=|\left\{y:y\beta V\left(G\right):\left(x,y\right)\beta E\left(G\right)\right\}|$ and ${d}_{G}^{-}\left(x\right)=|\left\{y:y\beta V\left(G\right):\left(y,x\right)\beta E\left(G\right)\right\}|$.

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

• Given two digraph ${G}_{1}$ and ${G}_{2}$ such that $V\left({G}_{1}\right)\beta ©V\left({G}_{2}\right)=\mathrm{\beta  }$, ${G}_{1}\beta {G}_{2}$ denotes the graph whose vertices set is $V\left({G}_{1}\right)\beta ͺV\left({G}_{2}\right)$ and whose arcs set is $E\left({G}_{1}\right)\beta ͺE\left({G}_{2}\right)$.

• Given a graph parameter $\mathrm{\pi }\beta \left\{\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right\}$, a digraph $G$ and an integer $k$, $\mathrm{\pi \pi }\left(G,k\right)$ 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, ${\mathrm{\pi \pi \pi }}_{\mathrm{\pi Έ\pi ½\pi Έ\pi \pi Έ\pi °\pi »}}$ will denote the number of connected components of the initial graph (i.e.,Β the graph induced by the constraint under consideration), $\mathrm{\pi \pi \pi }$ will denote the number of connected components of the final graph (i.e.,Β a subgraph of the initial graph). The use of $\mathrm{\pi \pi \pi }\left(G\right)$ will denote the number of connected components of the digraph $G$.

Given a global constraint $C$, and a graph parameter $\mathrm{\pi }$ used in the description of $C$, $\underset{Μ²}{\mathrm{\pi }}$ (respectively $\stackrel{Β―}{\mathrm{\pi }}$) denotes a lower bound (respectively upper bound) of $\mathrm{\pi }$ 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}=\left(V\left({G}_{f}\right),E\left({G}_{f}\right)\right)$ associated with a global constraint and give an example of constraint where they are used:

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ : largest distance between sources and sinks in the reduced graph associated with ${G}_{f}$ (adjacent vertices are at a distance of 1).

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint uses the graph property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }=1$ in order to force each vertex of the final graph to have at most one predecessor.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ : number of vertices of the largest connected component of ${G}_{f}$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi \pi Έ\pi \pi ΄},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi ²\pi \pi }\right)$ constraint uses the graph property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }=\mathrm{\pi \pi Έ\pi \pi ΄}$ in order to catch in $\mathrm{\pi \pi Έ\pi \pi ΄}$ the maximum number of consecutive variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection for which constraint $\mathrm{\pi ²\pi \pi }$ holds.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ : number of vertices of the largest strongly connected component of ${G}_{f}$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi }$ 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 $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ $\beta €$ 1 in order to avoid to have any circuit involving more than one vertex.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi }$ constraint enforces to cover a graph with a Hamiltonian cycle. It uses the graph -property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }=2$ to enforce that each vertex of ${G}_{f}$ have at most twoSince the $\mathrm{\pi \pi \pi \pi }$ constraint uses the arc generator the vertices of ${G}_{f}$ do not have any loop. successors.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ : 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 $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ is currently not used by any constraint.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi }$ constraint enforces to cover a graph with a Hamiltonian cycle. It uses the graph -property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }=2$ to enforce that each vertex of ${G}_{f}$ have at most twoSince the $\mathrm{\pi \pi \pi \pi }$ constraint uses the arc generator the vertices of ${G}_{f}$ do not have any loop. predecessors.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ : number of vertices of the smallest connected component of ${G}_{f}$.

EXAMPLE: Within the $\mathrm{\pi \pi \pi \pi \pi }$ 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 $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }=\mathrm{\pi Ό\pi Έ\pi ½}_\mathrm{\pi \pi Έ\pi \pi ΄}$ enforces that the smallest sequence of such variables consist of $\mathrm{\pi Ό\pi Έ\pi ½}_\mathrm{\pi \pi Έ\pi \pi ΄}$ variables.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ : number of vertices of the smallest strongly connected component of ${G}_{f}$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$$\left(NODES\right)$ constraint enforces covering a digraph with one circuit visiting once all its vertices. The graph -property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }=|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ enforces that the smallest strongly connected component of ${G}_{f}$ contain $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ vertices. Since $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ 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 $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint asks for some other properties. for having a circuit visiting once all vertices.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi }$ constraint enforces to cover a graph with a Hamiltonian cycle. It uses the graph -property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }=2$ to enforce that each vertex of ${G}_{f}$ have at most twoSince the $\mathrm{\pi \pi \pi \pi }$ constraint uses the arc generator the vertices of ${G}_{f}$ do not have any loop. successors.

• $\mathrm{\pi \pi \pi \pi }$ : cardinality of the set $E\left({G}_{f}\right)$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$ constraint enforces that each variable of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ take a value that is distinct from all the values assigned to the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

This is imposed by creating an arc from each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ to each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$. To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. Finally, the graph property $\mathrm{\pi \pi \pi \pi }=0$ forces ${G}_{f}$ to be empty so that no value is both assigned to a variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ as well as to a variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

• $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi }$ : cardinality of the set $E\left({G}_{f}\right)$ without considering the arcs linking the same vertex (i.e.,Β a loop).

• $\mathrm{\pi \pi \pi }$ : number of connected components of ${G}_{f}$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi }$ constraint covers a digraph by $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ trees in such a way that each vertex belongs to a distinct tree. It uses the graph -property $\mathrm{\pi \pi \pi }=\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ in order to state that ${G}_{f}$ is made up from $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ connected components.

• $\mathrm{\pi \pi \pi \pi }$ : number of strongly connected components of ${G}_{f}$.

EXAMPLE: The constraint $\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi  \pi °\pi »},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ forces $\mathrm{\pi ½\pi  \pi °\pi »}$ to be equal to the number of distinct values assigned to the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. This is enforced by using the graph -property $\mathrm{\pi \pi \pi \pi }=\mathrm{\pi ½\pi  \pi °\pi »}$. Each strongly connected component of the final graph corresponds to the variables that are assigned to the same value.

• $\mathrm{\pi \pi \pi \pi \pi }$ : number of vertices of ${G}_{f}$ that do not have any successor.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$ enforces that the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ collection correspond to the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ collection according to a permutation.

We first create an arc from each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ to each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$. To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. We use the graph -property $\mathrm{\pi \pi \pi \pi \pi }=|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}|$ in order to express the fact that each value assigned to a variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ should also be assigned to a variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$.

• $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi ²},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$ constraint enforces $\mathrm{\pi ²}$ to be the minimum number of values to change in the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ collections of variablesBoth collections have the same number of variables., so that the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ correspond to the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ according to a permutation.

A connected component ${\mathrm{\pi }}_{\mathrm{\pi £\pi \pi }}$ of the final graph ${G}_{f}$ corresponds to all variables that are assigned to the same value $\mathrm{\pi £\pi \pi }$: the sources and the sinks of ${\mathrm{\pi }}_{\mathrm{\pi £\pi \pi }}$ respectively correspond to the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ and to the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ that are assigned to $\mathrm{\pi £\pi \pi }$. 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 $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }=|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}|-\mathrm{\pi ²}$ for encoding the meaning of the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraint.

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ : number of vertices of ${G}_{f}$ that do not have any predecessor.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}\right)$ enforces that the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ collection correspond to the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$ collection according to a permutation.

We first create an arc from each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ to each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$. To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. We use the graph -property $\mathrm{\pi \pi \pi \pi \pi \pi \pi }=|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}|$ in order to express the fact that each value assigned to a variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{1}$ should also be assigned to a variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\mathtt{2}$.

• $\mathrm{\pi \pi \pi \pi \pi }$ : 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 $\mathrm{\pi \pi ’\pi \pi \pi }$$\left(\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄},\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\right)$ enforces that $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ 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 $\mathrm{\pi \pi \pi \pi \pi }=0$ enforces that all vertices of the final graph belong to a circuit.

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ : cardinality of the set $V\left({G}_{f}\right)$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi ²\pi \pi \pi \pi ΄\pi },\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\right)$ constraint considers a digraph with $n$ vertices described by the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection. It enforces that the subset of kept vertices of cardinality $n-\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi ²\pi \pi \pi \pi ΄\pi }$ and their corresponding arcs form a graph without a circuit. It uses the graph -property $\mathrm{\pi \pi \pi \pi \pi \pi \pi }=n-\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi ²\pi \pi \pi \pi ΄\pi }$ for enforcing that the final graph ${G}_{f}$ contain the required number of vertices.

• $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ 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 $\mathrm{\pi }$. For this purpose it uses the graph -property $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }=\mathrm{\pi }$.

• $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ : 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}$.

• $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ : 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 $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ±\pi °\pi »\pi °\pi ½\pi ²\pi ΄},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ constraint forces $\mathrm{\pi ±\pi °\pi »\pi °\pi ½\pi ²\pi ΄}$ 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 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. Each strongly connected component of ${G}_{f}$ corresponds to the variables that are assigned to the same value. The graph property $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }=\mathrm{\pi ±\pi °\pi »\pi °\pi ½\pi ²\pi ΄}$ allows for expressing this definition.

• $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$

• $\mathrm{\pi \pi \pi \pi }$ is an integer or an argument of type integer of the global constraint,

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ is an integer,

• $\mathrm{\pi \pi \pi \pi }$ 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 $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$. Let $\mathrm{\pi ±}$ denote the vertices of rank $\mathrm{\pi \pi \pi \pi }$ of ${G}_{f}$ from which we remove any loops.

• When $\mathrm{\pi ±}$ is not empty, it corresponds to the values of attribute $\mathrm{\pi \pi \pi \pi }$ of the items associated with the vertices of $\mathrm{\pi ±}$,

• Otherwise, when $\mathrm{\pi ±}$ is empty, it corresponds to the default value $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$.

EXAMPLE: The $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi Ό\pi Έ\pi ½},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$ forces $\mathrm{\pi Ό\pi Έ\pi ½}$ to be the minimum value of the collection of domain variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. There is an arc from a variable ${\mathrm{\pi \pi \pi }}_{1}$ to a variable ${\mathrm{\pi \pi \pi }}_{2}$ if and only if ${\mathrm{\pi \pi \pi }}_{1}<{\mathrm{\pi \pi \pi }}_{2}$. The graph -property $\mathrm{\pi \pi \pi \pi \pi }\left(0,\mathrm{\pi Ό\pi °\pi \pi Έ\pi ½\pi },\mathrm{\pi \pi \pi }\right)=\mathrm{\pi Ό\pi Έ\pi ½}$ expresses the fact that $\mathrm{\pi Ό\pi Έ\pi ½}$ is equal to the value of the source of ${G}_{f}$ (since $\mathrm{\pi \pi \pi \pi }=0$).

• $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi  \pi \pi \pi }_\mathrm{\pi \pi }\left(\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi }\right)$

• $\mathrm{\pi \pi \pi \pi }$ is an attribute corresponding to an integer that occurs in all the collections that were used for generating the vertices of the initial graph,

• $\mathrm{\pi \pi \pi \pi }$ is an integer or an argument of type integer of the global constraint,

• $\mathrm{\pi \pi }$ is an integer or an argument of type integer of the global constraint.

Let $\mathrm{\beta ±}$ (respectively $\mathrm{\pi ―}$) denote the vertices of ${G}_{f}$ such that $\mathrm{\pi \pi \pi \pi }$ is equal to $\mathrm{\pi \pi \pi \pi }$ (respectively $\mathrm{\pi \pi }$). $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi  \pi \pi \pi }_\mathrm{\pi \pi }\left(\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi }\right)$ is equal to 1 if there exists a path between each vertex of $\mathrm{\beta ±}$ and each vertex of $\mathrm{\pi ―}$, and 0 if there exists no path between a vertex of $\mathrm{\beta ±}$ and a vertex of $\mathrm{\pi ―}$.

• $\mathrm{\pi \pi \pi \pi }$ is an attribute corresponding to an integer that occurs in all the collections that were used for generating the vertices of the initial graph,

• $\mathrm{\pi \pi \pi \pi }$ 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,

• $\mathrm{\pi \pi }$ 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:

• ${\mathrm{\beta ±}}_{v}$ the set of vertices for which the value of the attribute $\mathrm{\pi \pi \pi \pi }$ is equal to the $\mathrm{\pi \pi \pi \pi }$ attribute (or is included within the $\mathrm{\pi \pi \pi \pi }$ attribute when it corresponds to a set of integers).

• ${\mathrm{\pi ―}}_{v}$ the set of vertices for which the value of the attribute $\mathrm{\pi \pi \pi \pi }$ is equal to the $\mathrm{\pi \pi }$ attribute (or is included within the $\mathrm{\pi \pi }$ attribute when it corresponds to a set of integers).

$\mathrm{\pi \pi \pi \pi }_\mathrm{\pi  \pi \pi \pi }_\mathrm{\pi \pi }\left(\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi }\right)$ is equal to

• 1 if for each vertex of ${G}_{f}$ there exists a path between each vertex of ${\mathrm{\beta ±}}_{v}$ and each vertex of ${\mathrm{\pi ―}}_{v}$.

• 0 if for a vertex of ${G}_{f}$ there is no path between a vertex of ${\mathrm{\beta ±}}_{v}$ and a vertex of ${\mathrm{\pi ―}}_{v}$.

• $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$

• $\mathrm{\pi \pi \pi }$ is a collection that was used for generating the vertices of the initial graph,

• $\mathrm{\pi \pi \pi \pi }$ is an attribute corresponding to an integer or to a domain variable of the collection $\mathrm{\pi \pi \pi }$.

Let $\mathrm{\pi ±}$ be the set of vertices of ${G}_{f}$ that were generated from the items of the collection $\mathrm{\pi \pi \pi }$.

• If $\mathrm{\pi ±}$ is not empty, $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$ corresponds to the product of the values of attribute $\mathrm{\pi \pi \pi \pi }$ associated with the vertices of $\mathrm{\pi ±}$,

• Otherwise, if $\mathrm{\pi ±}$ is empty, $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$ is equal to 1.

EXAMPLE: The constraint $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi ²\pi \pi },\mathrm{\pi  \pi °\pi }\right)$ forces the product of the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection to be equal, less than or equal, ... to a given domain variable $\mathrm{\pi  \pi °\pi }$.

To each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the $\mathrm{\pi \pi Έ\pi Ώ\pi Ή}$ arc generator together with the $\mathrm{\pi \pi \pi \pi ΄}$ arc constraint. Finally, $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)\mathrm{\pi ²\pi \pi }\mathrm{\pi  \pi °\pi }$ expresses the required condition. In this expression $\mathrm{\pi \pi \pi }$ and $\mathrm{\pi ²\pi \pi }$ respectively corresponds to the attribute of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ (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 $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ corresponds to the product of the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

• $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$

• $\mathrm{\pi \pi \pi }$ is a collection that was used for generating the vertices of the initial graph,

• $\mathrm{\pi \pi \pi \pi }$ is an attribute corresponding to an integer or to a domain variable of the collection $\mathrm{\pi \pi \pi }$.

Let $\mathrm{\pi ±}$ be the set of vertices of ${G}_{f}$ that were generated from the items of the collection $\mathrm{\pi \pi \pi }$.

• If $\mathrm{\pi ±}$ is not empty, $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$ corresponds to the difference between the maximum and the minimum values of attribute $\mathrm{\pi \pi \pi \pi }$ associated with the vertices of $\mathrm{\pi ±}$,

• Otherwise, if $\mathrm{\pi ±}$ is empty, $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$ is equal to 0.

EXAMPLE: The constraint $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi ²\pi \pi },\mathrm{\pi  \pi °\pi }\right)$ forces the difference between the maximum value and the minimum value of the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection to be equal, less than or equal, ... to a given domain variable $\mathrm{\pi  \pi °\pi }$.

To each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the $\mathrm{\pi \pi Έ\pi Ώ\pi Ή}$ arc generator together with the $\mathrm{\pi \pi \pi \pi ΄}$ arc constraint. Finally, $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)\mathrm{\pi ²\pi \pi }\mathrm{\pi  \pi °\pi }$ expresses the required condition. In this expression $\mathrm{\pi \pi \pi }$ and $\mathrm{\pi ²\pi \pi }$ respectively corresponds to the attribute of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ (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 $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ corresponds to the difference between the maximum value and the minimum value of the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

• $\mathrm{\pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$

• $\mathrm{\pi \pi \pi }$ is a collection that was used for generating the vertices of the initial graph,

• $\mathrm{\pi \pi \pi \pi }$ is an attribute corresponding to an integer or to a domain variable of the collection $\mathrm{\pi \pi \pi }$.

Let $\mathrm{\pi ±}$ be the set of vertices of ${G}_{f}$ that were generated from the items of the collection $\mathrm{\pi \pi \pi }$.

• If $\mathrm{\pi ±}$ is not empty, $\mathrm{\pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$ corresponds to the sum of the values of attribute $\mathrm{\pi \pi \pi \pi }$ associated with the vertices of $\mathrm{\pi ±}$,

• Otherwise, if $\mathrm{\pi ±}$ is empty, $\mathrm{\pi \pi \pi }\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }\right)$ is equal to 0.

EXAMPLE: The constraint $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi ²\pi \pi },\mathrm{\pi  \pi °\pi }\right)$ forces the sum of the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection to be equal, less than or equal, ... to a given domain variable $\mathrm{\pi  \pi °\pi }$.

To each variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the $\mathrm{\pi \pi Έ\pi Ώ\pi Ή}$ arc generator together with the $\mathrm{\pi \pi \pi \pi ΄}$ arc constraint. Finally, $\mathrm{\pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)\mathrm{\pi ²\pi \pi }\mathrm{\pi  \pi °\pi }$ expresses the required condition. In this expression $\mathrm{\pi \pi \pi }$ and $\mathrm{\pi ²\pi \pi }$ respectively correspond to the attribute of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ (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 $\mathrm{\pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ corresponds to the sum of the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

• $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }\left(\mathrm{\pi ΄\pi ‘\pi \pi }\right)$ $\mathrm{\pi ΄\pi ‘\pi \pi }$ is an arithmetic expression. For each arc $a$ of $E\left({G}_{f}\right)$, let $f\left(a\right)$ denote the value of $\mathrm{\pi ΄\pi ‘\pi \pi }$. $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }\left(\mathrm{\pi ΄\pi ‘\pi \pi }\right)$ is equal to ${\beta }_{a\beta E\left({G}_{f}\right)}f\left(a\right)$. The value of $\mathrm{\pi ΄\pi ‘\pi \pi }$ usually depends on the attributes of the items located at the extremities of an arc.

EXAMPLE: The constraint $\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi Ό\pi °\pi \pi \pi Έ\pi },\mathrm{\pi ²\pi Ύ\pi \pi }\right)$ enforces that each value $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi }$ be assigned to exactly $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. In addition the $\mathrm{\pi ²\pi Ύ\pi \pi }$ 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 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection to the ${j}^{th}$ value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection. These elementary costs are given by the $\mathrm{\pi Ό\pi °\pi \pi \pi Έ\pi }$ collection.

The graph -property $\mathrm{\pi \pi \pi Ό}_\mathrm{\pi \pi ΄\pi Έ\pi Ά\pi ·\pi }_\mathrm{\pi °\pi \pi ²}\left(\mathrm{\pi Ό\pi °\pi \pi \pi Έ\pi }\left[\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi ’}-1\right)*\mathrm{\pi \pi \pi £\pi }\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)+\mathrm{\pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi ’}\right].\mathrm{\pi }\right)=\mathrm{\pi ²\pi Ύ\pi \pi }$ expresses the fact that the $\mathrm{\pi ²\pi Ύ\pi \pi }$ variable is equal to the sum of the elementary costs associated with each variable -value assignment. All these elementary costs are recorded in the $\mathrm{\pi Ό\pi °\pi \pi \pi Έ\pi }$ collection. More precisely, the cost ${c}_{ij}$ is recorded in the attribute $\mathrm{\pi }$ of the ${\left(\left(i-1\right)*|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)|+j\right)}^{th}$ entry of the $\mathrm{\pi Ό\pi °\pi \pi \pi Έ\pi }$ collection.

A last graph parameter, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ , is computed on two final graphs ${G}_{1}$ and ${G}_{2}$ that have the same set $V$ of vertices and the sets $E\left({G}_{1}\right)$ and $E\left({G}_{2}\right)$ of arcs. This graph parameter is the cardinality of the set $\left(E\left({G}_{1}\right)-E\left({G}_{2}\right)\right)\beta ͺ\left(E\left({G}_{2}\right)-E\left({G}_{1}\right)\right)$. This corresponds to the number of arcs that belong to $E\left({G}_{1}\right)$ but not to $E\left({G}_{2}\right)$, plus the number of arcs that are in $E\left({G}_{2}\right)$ but not in $E\left({G}_{1}\right)$.

#### 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).

• $\mathrm{\pi °\pi ²\pi \pi ²\pi »\pi Έ\pi ²}$ : the final graph doesn't have any circuit.

• $\mathrm{\pi ±\pi Έ\pi Ώ\pi °\pi \pi \pi Έ\pi \pi ΄}$ : the final graph is bipartite.

• $\mathrm{\pi ²\pi Ύ\pi ½\pi \pi ΄\pi ²\pi \pi \pi Έ\pi  \pi ΄}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ\pi }_\mathrm{\pi °\pi \pi ΄}_\mathrm{\pi ²\pi Ύ\pi ½\pi ½\pi ΄\pi ²\pi \pi ΄\pi ³}$ : denotes the fact that the graph constraint of a global constraint uses only the $\mathrm{\pi \pi ΄\pi \pi »}$ and the $\mathrm{\pi Ώ\pi \pi \pi }$ 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.

• $\mathrm{\pi ΄\pi \pi \pi Έ\pi  \pi °\pi »\pi ΄\pi ½\pi ²\pi ΄}$ : the final graph is reflexive, symmetric and transitive.

• $\mathrm{\pi ½\pi Ύ}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ}$ : the final graph doesn't have any loop.

• $\mathrm{\pi Ύ\pi ½\pi ΄}_\mathrm{\pi \pi \pi ²\pi ²}$ : the vertices of the initial graph belong to the final graph and all vertices of the final graph have exactly one successor.

• $\mathrm{\pi \pi \pi Ό\pi Ό\pi ΄\pi \pi \pi Έ\pi ²}$ : 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$.