## 5.89. cycle

 DESCRIPTION LINKS GRAPH
Origin
Constraint

$\mathrm{𝚌𝚢𝚌𝚕𝚎}\left(\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴},\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}\ge 1$ $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$
Purpose

Consider a digraph $G$ described by the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection. $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ is equal to the number of circuits for covering $G$ in such a way that each vertex of $G$ belongs to one single circuit. $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ can also be interpreted as the number of cycles of the permutation associated with the successor variables of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection.

Example
$\left(\begin{array}{c}2,〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚜𝚞𝚌𝚌}-2,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚜𝚞𝚌𝚌}-1,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-3\hfill & \mathrm{𝚜𝚞𝚌𝚌}-5,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-4\hfill & \mathrm{𝚜𝚞𝚌𝚌}-3,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-5\hfill & \mathrm{𝚜𝚞𝚌𝚌}-4\hfill \end{array}〉\hfill \end{array}\right)$

In this example we have the following 2 ($\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}=2$) cycles: $1\to 2\to 1$ and $3\to 5\to 4\to 3$. Consequently, the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint holds.

Typical
 $|\mathrm{𝙽𝙾𝙳𝙴𝚂}|>2$ $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}<|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$
Symmetry

Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

Usage

The PhD thesis of Éric Bourreau [Bourreau99] mentions the following applications of extensions of the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint:

• The balanced Euler knight problem where one tries to cover a rectangular chessboard of size $N·M$ by $C$ knights that all have to visit between $2·⌊⌊\left(N·M\right)/C⌋/2⌋$ and $2·⌈⌈\left(N·M\right)/C⌉/2⌉$ distinct locations. For some values of $N$, $M$ and $C$ there does not exist any solution to the previous problem. This is for instance the case when $N=M=C=6$. Figure 5.89.1 depicts the graph associated with the $6×6$ chessboard as well as examples of balanced solutions with respectively 1, 2, 3, 4 and 5 knights.

• Some pick-up delivery problems where a fleet of vehicles has to transport a set of orders. Each order is characterised by its initial location, its final destination and its weight. In addition one also has to take into account the capacity of the different vehicles.

##### Figure 5.89.1. Graph of potential moves of the $6×6$ chessboard and corresponding balanced tours Remark

In the original $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint of CHIP the $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.

In an early version of the CHIP there was a constraint named $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ that, from a declarative point of view, was equivalent to $\mathrm{𝚌𝚢𝚌𝚕𝚎}\left(1,\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$. In ALICE [Lauriere78] the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint was also present.

Given a complete digraph of $n$ vertices as well as an unrestricted number of circuits $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$, the total number of solutions of the corresponding $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint corresponds to the sequence A000142 of the On -Line Encyclopedia of Integer Sequences [Sloane10]. Given a complete digraph of $n$ vertices as well as a fixed number of circuits $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ between 1 and $n$, the total number of solutions of the corresponding $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint corresponds to the so called Stirling number of first kind.

Algorithm

Since all $\mathrm{𝚜𝚞𝚌𝚌}$ variables have to take distinct values one can reuse the algorithms associated with the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint. A second necessary condition is to have no more than $\overline{\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}}$ strongly connected components. Pruning for enforcing this condition, as soon as we have $\overline{\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}}$ strongly connected components, can be done by forcing all strong bridges to belong to the final solution, since otherwise we would have more than $\overline{\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}}$ strongly connected components. Since all the vertices of a circuit belong to the same strongly connected component an arc going from one strongly connected component to another strongly connected component has to be removed.

See also

specialisation: $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ ($\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ set to 1).

Keywords
Arc input(s)

$\mathrm{𝙽𝙾𝙳𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{1},\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{1}.\mathrm{𝚜𝚞𝚌𝚌}=\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{2}.\mathrm{𝚒𝚗𝚍𝚎𝚡}$
Graph property(ies)
 $•$$\mathrm{𝐍𝐓𝐑𝐄𝐄}$$=0$ $•$$\mathrm{𝐍𝐂𝐂}$$=\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$

Graph class
$\mathrm{𝙾𝙽𝙴}_\mathrm{𝚂𝚄𝙲𝙲}$

Graph model

From the restrictions and from the arc constraint, we deduce that we have a bijection from the successor variables to the values of interval $\left[1,|\mathrm{𝙽𝙾𝙳𝙴𝚂}|\right]$. With no explicit restrictions it would have been impossible to derive this property.

In order to express the binary constraint that links two vertices one has to make explicit the identifier of the vertices. This is why the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint considers objects that have two attributes:

• One fixed attribute $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ that is the identifier of the vertex,

• One variable attribute $\mathrm{𝚜𝚞𝚌𝚌}$ that is the successor of the vertex.

The graph property $\mathrm{𝐍𝐓𝐑𝐄𝐄}$ $=$ 0 is used in order to avoid having vertices that both do not belong to a circuit and have at least one successor located on a circuit. This concretely means that all vertices of the final graph should belong to a circuit.

Parts (A) and (B) of Figure 5.89.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐂𝐂}$ graph property, we show the two connected components of the final graph. The constraint holds since all the vertices belong to a circuit (i.e., $\mathrm{𝐍𝐓𝐑𝐄𝐄}$ $=$ 0) and since $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ $=$ $\mathrm{𝐍𝐂𝐂}$ $=$ 2.

##### Figure 5.89.2. Initial and final graph of the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint  (a) (b)