N. Beldiceanu

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

The first $\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.403.1.

Figure 5.403.1. The two trees corresponding to the first example of the Example slot; each vertex contains the information $\mathrm{𝚒𝚗𝚍𝚎𝚡}|\mathrm{𝚜𝚞𝚌𝚌}$ where $\mathrm{𝚜𝚞𝚌𝚌}$ is the index of its father in the tree (by convention the father of the root is the root itself).

Figure 5.403.2 gives all solutions to the following non ground instance of the $\mathrm{𝚝𝚛𝚎𝚎}$ constraint: $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}\in [3,4]$, $S_1\in [1,2]$, $S_2\in [1,3]$, $S_3\in [1,4]$, $S_4\in [2,4]$, $\mathrm{𝚝𝚛𝚎𝚎}$$(\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂},\langle 1S_1,2S_2,3S_3,4S_4\rangle )$.

Figure 5.403.2. All solutions corresponding to the non ground example of the $\mathrm{𝚝𝚛𝚎𝚎}$ constraint of the All solutions slot (the $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute is displayed as indices of the $\mathrm{𝚜𝚞𝚌𝚌}$ attribute)

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

Functional dependency: $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$ determined by $\mathrm{𝙽𝙾𝙳𝙴𝚂}$.

Given a complete digraph of $n$ vertices as well as an unrestricted number of trees $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$, the total number of solutions to the corresponding $\mathrm{𝚝𝚛𝚎𝚎}$ constraint corresponds to the sequence A000272 of the On-Line Encyclopaedia 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 and only 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{𝙼𝙰𝚇𝚃𝚁𝙴𝙴𝚂}]$.

Inspired by the idea of using dominators used in [ItalianoLauraSantaroni10] for getting a linear time algorithm for computing strong articulation points of a digraph $G$, the worst case complexity of the algorithm proposed in [BeldiceanuFlenerLorca05] was also enhanced in a similar way by J.-G. Fages and X. Lorca [FagesLorca11].

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+\cdots +B_{\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|}$ for stating the fact that the number of trees is equal to the number of loops of the graph.

Number of solutions for $\mathrm{𝚝𝚛𝚎𝚎}$: domains $0..n$

Solution count for $\mathrm{𝚝𝚛𝚎𝚎}$: domains $0..n$

tree in Choco.

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

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

implies (items to collection): $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}\_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$.

related: $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}\_\mathrm{𝚝𝚛𝚎𝚎}$ (counting number of trees versus controlling how balanced the trees are), $\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: DFS-bottleneck, strong articulation point, arc-consistency.

final graph structure: connected component, tree, one_succ.

modelling: functional dependency.