N. Beldiceanu

$\mathrm{𝚝𝚛𝚎𝚎}(\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂},\mathrm{𝙽𝙾𝙳𝙴𝚂})$

The $\mathrm{𝚝𝚛𝚎𝚎}$ constraint holds since the graph associated with the items of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection corresponds to two trees (i.e., $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}=2$): each tree respectively involves the vertices $\{1,2,3,5,6,8\}$ and $\{4,7\}$. They are depicted by Figure 5.337.1.

Figure 5.337.1. The two trees associated with the example

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

Given a complete digraph of $n$ vertices as well as an unrestricted number of trees $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$, the total number of solutions of the corresponding $\mathrm{𝚝𝚛𝚎𝚎}$ constraint corresponds to the sequence A000272 of the On -Line Encyclopedia of Integer Sequences [Sloane10].

Extension of the $\mathrm{𝚝𝚛𝚎𝚎}$ constraint to the minimum spanning tree constraint is described in [DoomsKatriel06], [Regin08], [ReginRousseauRueherHoeve10].

An arc-consistency filtering algorithm for the $\mathrm{𝚝𝚛𝚎𝚎}$ constraint is described in [BeldiceanuFlenerLorca05]. This algorithm is based on a necessary and sufficient condition that we now depict.

To any $\mathrm{𝚝𝚛𝚎𝚎}$ constraint we associate the digraph $G=(V,E)$, where:

• To each item $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right]$ of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection corresponds a vertex $v_i$ of $G$.

• For every pair of items $\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}\right[i],\mathrm{𝙽𝙾𝙳𝙴𝚂}[j\left]\right)$ of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection, where $i$ and $j$ are not necessarily distinct, there is an arc from $v_i$ to $v_j$ in $E$ if $j$ is a potential value of $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚜𝚞𝚌𝚌}$.

A strongly connected component $C$ of $G$ is called a sink component if all the successors of all vertices of $C$ belong to $C$. Let $\mathrm{𝙼𝙸𝙽𝚃𝚁𝙴𝙴𝚂}$ and $\mathrm{𝙼𝙰𝚇𝚃𝚁𝙴𝙴𝚂}$ respectively denote the number of sink components of $G$ and the number of vertices of $G$ with a loop.

The $\mathrm{𝚝𝚛𝚎𝚎}$ constraint has a solution if and only if:

• Each sink component of $G$ contains at least one vertex with a loop,

• The domain of $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$ has at least one value within interval $[\mathrm{𝙼𝙸𝙽𝚃𝚁𝙴𝙴𝚂},\mathrm{𝙼𝙰𝚇𝚃𝚁𝙴𝙴𝚂}]$.

Most likely, the worst case complexity of the algorithm proposed in [BeldiceanuFlenerLorca05] may be enhanced by using the linear time algorithm presented in [ItalianoLauraSantaroni10] for computing the strong articulation points of the digraph $G$.

The $\mathrm{𝚝𝚛𝚎𝚎}$ constraint can be expressed in term of (1) a set of ${\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|}^2$ reified constraints for avoiding circuit between more than one node and of (2) $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ reified constraints and of one sum constraint for counting the trees:

1. For each vertex $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right]$ $(i\in [1,\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|\left]\right)$ of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection we create a variable $R_i$ that takes its value within interval $[1,|\mathrm{𝙽𝙾𝙳𝙴𝚂}\left|\right]$. This variable represents the rank of vertex $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right]$ within a solution. It is used to prevent the creation of circuit involving more than one vertex as explained now. For each pair of vertices $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right],\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[j\right]$ $(i,j\in [1,\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|\left]\right)$ of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection we create a reified constraint of the form $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚜𝚞𝚌𝚌}=\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[j\right].\mathrm{𝚒𝚗𝚍𝚎𝚡}\wedge i\ne j\Rightarrow R_i<R_j$. The purpose of this constraint is to express the fact that, if there is an arc from vertex $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right]$ to another vertex $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[j\right]$, then $R_i$ should be strictly less than $R_j$.

2. For each vertex $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right]$ $(i\in [1,\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|\left]\right)$ of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection we create a 0-1 variable $B_i$ and state the following reified constraint $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚜𝚞𝚌𝚌}=\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚒𝚗𝚍𝚎𝚡}\iff B_i$ in order to force variable $B_i$ to be set to value 1 if and only if there is a loop on vertex $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right]$. Finally we create a constraint $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}=B_1+B_2+...+B_{\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|}$ for stating the fact that the number of trees is equal to the number of loops of the graph.

tree in Choco.

common keyword: $\mathrm{𝚌𝚢𝚌𝚕𝚎}$, $\mathrm{𝚐𝚛𝚊𝚙𝚑}\_\mathrm{𝚌𝚛𝚘𝚜𝚜𝚒𝚗𝚐}$, $\mathrm{𝚖𝚊𝚙}$ (graph partitioning constraint), $\mathrm{𝚙𝚛𝚘𝚙𝚎𝚛}\_\mathrm{𝚏𝚘𝚛𝚎𝚜𝚝}$ (connected component,tree).

implied by: $\mathrm{𝚋𝚒𝚗𝚊𝚛𝚢}\_\mathrm{𝚝𝚛𝚎𝚎}$.

related: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}\_\mathrm{𝚗𝚘}\_\mathrm{𝚕𝚘𝚘𝚙}$, $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚗𝚘}\_\mathrm{𝚕𝚘𝚘𝚙}$ (can be used for restricting number of children since discard loops associated with tree roots).

shift of concept: $\mathrm{𝚜𝚝𝚊𝚋𝚕𝚎}\_\mathrm{𝚌𝚘𝚖𝚙𝚊𝚝𝚒𝚋𝚒𝚕𝚒𝚝𝚢}$, $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚊𝚗𝚐𝚎}$, $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$.

specialisation: $\mathrm{𝚋𝚒𝚗𝚊𝚛𝚢}\_\mathrm{𝚝𝚛𝚎𝚎}$ (no limit on the number of children replaced by at most two children), $\mathrm{𝚙𝚊𝚝𝚑}$ (no limit on the number of children replaced by at most one child).

uses in its reformulation: $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚊𝚗𝚐𝚎}$, $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$.

constraint type: graph constraint, graph partitioning constraint.

filtering: strong articulation point, arc-consistency.

final graph structure: connected component, tree, one_succ.

$\mathrm{𝙽𝙾𝙳𝙴𝚂}$

We use the graph property $\mathrm{𝐌𝐀𝐗}\_\mathrm{𝐍𝐒𝐂𝐂}\le 1$ in order to specify the fact that the size of the largest strongly connected component should not exceed one. In fact each root of a tree is a strongly connected component with one single vertex. The second graph property $\mathrm{𝐍𝐂𝐂}=\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$ enforces the number of trees to be equal to the number of connected components.

Parts (A) and (B) of Figure 5.337.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐂𝐂}$ graph property, we display the two connected components of the final graph. Each of them corresponds to a tree. The $\mathrm{𝚝𝚛𝚎𝚎}$ constraint holds since all strongly connected components of the final graph have no more than one vertex and since $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}=\mathrm{𝐍𝐂𝐂}=2$.

Figure 5.337.2. Initial and final graph of the $\mathrm{𝚝𝚛𝚎𝚎}$ constraint

(a)	(b)