## 5.89. cycle

Origin
Constraint

$\mathrm{\pi \pi ’\pi \pi \pi }\left(\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄},\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\right)$

Arguments
 $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi ‘}-\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}\beta ₯1$ $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi },\left[\mathrm{\pi \pi \pi \pi \pi ‘},\mathrm{\pi \pi \pi \pi }\right]\right)$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi ‘}\beta ₯1$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi ‘}\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi },\mathrm{\pi \pi \pi \pi \pi ‘}\right)$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi }\beta ₯1$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi }\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$
Purpose

Consider a digraph $G$ described by the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection. $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ 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{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ can also be interpreted as the number of cycles of the permutation associated with the successor variables of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection.

Example
$\left(\begin{array}{c}2,β©\begin{array}{cc}\mathrm{\pi \pi \pi \pi \pi ‘}-1\hfill & \mathrm{\pi \pi \pi \pi }-2,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-2\hfill & \mathrm{\pi \pi \pi \pi }-1,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-3\hfill & \mathrm{\pi \pi \pi \pi }-5,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-4\hfill & \mathrm{\pi \pi \pi \pi }-3,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-5\hfill & \mathrm{\pi \pi \pi \pi }-4\hfill \end{array}βͺ\hfill \end{array}\right)$

In this example we have the following 2 ($\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}=2$) cycles: $1\beta 2\beta 1$ and $3\beta 5\beta 4\beta 3$. Consequently, the $\mathrm{\pi \pi ’\pi \pi \pi }$ constraint holds.

Typical
 $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|>2$ $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}<|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$
Symmetry

Items of $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ are permutable.

Usage

The PhD thesis of ΓricΒ BourreauΒ [Bourreau99] mentions the following applications of extensions of the $\mathrm{\pi \pi ’\pi \pi \pi }$ 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Β·\beta \beta \left(NΒ·M\right)/C\beta /2\beta $ and $2Β·\beta \beta \left(NΒ·M\right)/C\beta /2\beta $ 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\Gamma 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.

Remark

In the original $\mathrm{\pi \pi ’\pi \pi \pi }$ constraint of CHIP the $\mathrm{\pi \pi \pi \pi \pi ‘}$ 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{\pi \pi \pi \pi \pi \pi \pi }$ that, from a declarative point of view, was equivalent to $\mathrm{\pi \pi ’\pi \pi \pi }\left(1,\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\right)$. In ALICE [Lauriere78] the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint was also present.

Given a complete digraph of $n$ vertices as well as an unrestricted number of circuits $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$, the total number of solutions of the corresponding $\mathrm{\pi \pi ’\pi \pi \pi }$ 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{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ between 1 and $n$, the total number of solutions of the corresponding $\mathrm{\pi \pi ’\pi \pi \pi }$ constraint corresponds to the so called Stirling number of first kind.

Algorithm

Since all $\mathrm{\pi \pi \pi \pi }$ variables have to take distinct values one can reuse the algorithms associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. A second necessary condition is to have no more than $\stackrel{Β―}{\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}}$ strongly connected components. Pruning for enforcing this condition, as soon as we have $\stackrel{Β―}{\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}}$ strongly connected components, can be done by forcing all strong bridges to belong to the final solution, since otherwise we would have more than $\stackrel{Β―}{\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}}$ 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.

specialisation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ set to 1).

Keywords
Arc input(s)

$\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi ‘}$
Graph property(ies)
 $\beta ’$$\mathrm{\pi \pi \pi \pi \pi }$$=0$ $\beta ’$$\mathrm{\pi \pi \pi }$$=\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$

Graph class
$\mathrm{\pi Ύ\pi ½\pi ΄}_\mathrm{\pi \pi \pi ²\pi ²}$

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{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\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{\pi \pi ’\pi \pi \pi }$ constraint considers objects that have two attributes:

• One fixed attribute $\mathrm{\pi \pi \pi \pi \pi ‘}$ that is the identifier of the vertex,

• One variable attribute $\mathrm{\pi \pi \pi \pi }$ that is the successor of the vertex.

The graph property $\mathrm{\pi \pi \pi \pi \pi }$ $=$ 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{\pi \pi \pi }$ 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{\pi \pi \pi \pi \pi }$ $=$ 0) and since $\mathrm{\pi ½\pi ²\pi \pi ²\pi »\pi ΄}$ $=$ $\mathrm{\pi \pi \pi }$ $=$ 2.