## 5.55. binary_tree

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\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 ₯0$ $\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

Cover the digraph $G$ described by the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection with $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ binary trees in such a way that each vertex of $G$ belongs to exactly one binary tree (i.e.,Β each vertex of $G$ has at most two children). The edges of the binary trees are directed from their leaves to their respective root.

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

The first $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$ constraint holds since its second argument corresponds to the 2 (i.e.,Β the first argument of the first $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$ constraint) binary trees depicted by FigureΒ 5.55.1.

All solutions

FigureΒ 5.55.2 gives all solutions to the following non ground instance of the $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$ constraint: $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }\beta \left\{1,4\right\}$, ${S}_{1}\beta \left[1,2\right]$, ${S}_{2}\beta \left[1,3\right]$, ${S}_{3}\beta \left[3,4\right]$, ${S}_{4}\beta \left[3,4\right]$, ${S}_{5}\beta \left[2,3\right]$, $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi },\beta ©1{S}_{1},2{S}_{2},3{S}_{3},4{S}_{4},5{S}_{5}\beta ͺ\right)$.

Typical
 $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }>0$ $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }<|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|>2$
Symmetry

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

Arg. properties

Functional dependency: $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ determined by $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$.

Reformulation

The $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$ constraint can be expressed in term of (1)Β a set of ${|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|}^{2}$ reified constraints for avoiding circuit between more than one node and of (2)Β $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ reified constraints and of one sum constraint for counting the trees and of (3)Β a set of ${|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|}^{2}$ reified constraints and of $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ inequalities constraints for enforcing the fact that each vertex has at most two children.

1. For each vertex $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right]$ $\left(i\beta \left[1,|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\right]\right)$ of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection we create a variable ${R}_{i}$ that takes its value within interval $\left[1,|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\right]$. This variable represents the rank of vertex $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\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{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right],\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[j\right]$ $\left(i,j\beta \left[1,|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\right]\right)$ of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection we create a reified constraint of the form . The purpose of this constraint is to express the fact that, if there is an arc from vertex $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right]$ to another vertex $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[j\right]$, then ${R}_{i}$ should be strictly less than ${R}_{j}$.

2. For each vertex $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right]$ $\left(i\beta \left[1,|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\right]\right)$ of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection we create a 0-1 variable ${B}_{i}$ and state the following reified constraint $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi \pi }=\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right].\mathrm{\pi \pi \pi \pi \pi ‘}\beta {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{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right]$. Finally we create a constraint $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }={B}_{1}+{B}_{2}+\beta ―+{B}_{|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|}$ for stating the fact that the number of trees is equal to the number of loops of the graph.

3. For each pair of vertices $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right],\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[j\right]$ $\left(i,j\beta \left[1,|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\right]\right)$ of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection we create a 0-1 variable ${B}_{ij}$ and state the following reified constraint . Variable ${B}_{ij}$ is set to value 1 if and only if there is an arc from $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[i\right]$ to $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[j\right]$. Then for each vertex $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\left[j\right]$ $\left(j\beta \left[1,|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|\right]\right)$ we create a constraint of the form ${B}_{1j}+{B}_{2j}+\beta ―+{B}_{|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|j}\beta €2$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 3 16 121 1191 14461 209098 3510921

Number of solutions for $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total3161211191144612090983510921
 Parameter value

129605406120837901345680
216484805850844201411200
3-112150210033390599760
4--1203606720135240
5---13073517640
6----1421344
7-----156
8------1

Solution count for $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$: domains $0..n$

generalisation: $\mathrm{\pi \pi \pi \pi }$Β (at most two childrens replaced by no restriction on maximum number of childrens).

specialisation: $\mathrm{\pi \pi \pi \pi }$Β (at most two childrens replaced by at most one child).

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 }_\mathrm{\pi \pi \pi \pi }$$\beta €1$ $\beta ’$$\mathrm{\pi \pi \pi }$$=\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ $\beta ’$$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$$\beta €2$

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

Graph model

We use the same graph constraint as for the $\mathrm{\pi \pi \pi \pi }$ constraint, except that we add the graph property $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ $\beta €$ 2, which constraints the maximum in-degree of the final graph to not exceed 2. $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ does not consider loops: This is why we do not have any problem with the root of each tree.

PartsΒ (A) andΒ (B) of FigureΒ 5.55.3 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $\mathrm{\pi \pi \pi }$ graph property, we display the two connected components of the final graph. Each of them corresponds to a binary tree. Since we use the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ graph property, we also show with a double circle a vertex that has a maximum number of predecessors.

The $\mathrm{\pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi }$ constraint holds since all strongly connected components of the final graph have no more than one vertex, since $\mathrm{\pi ½\pi \pi \pi ΄\pi ΄\pi }$ $=$ $\mathrm{\pi \pi \pi }$ $=$ 2 and since $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$ $=$ 2.