Cet algorithme est la suite du TP 5 sur les arbres binaires. Pour mettre tout le monde au même niveau, voici une correction du TP.
En particulier, le module des arbres binaires contient une fonction de dessin. Le fichier trivial_embedding peut être compilé en exécutable : il faut avant de l'exécuter créer un sous-repertoire pic dans lequel il mettra un dessin naïf de l'arbre complet.
Pour l'algorithme de placement des nœuds, il va être capital de représenter l'espace horizontal pris par un arbre, sous la forme d'un intervalle de la ligne des nombres réels. Un intervalle $[\mathit{lower},\mathit{upper}]$, avec $\mathit{lower} \leq \mathit{upper}$, est représenté par la donnée de ses deux extrémités $\mathit{lower}$ et $\mathit{upper}$, qui sont des flottants. Il y a aussi un intervalle particulier, l'intervalle vide.
Proposez un type pour les intervalles. Les fonctions pour ce type seront placées dans un fichier interval.ml. Ajoutez aussi une fonction de création d'un intervalle, et deux accesseurs.
Nous continuons avec plusieurs fonctions pour manipuler des intervalles.
Le décalage de l'intervalle $[\mathit{lower},\mathit{upper}]$ par un flottant $\delta$ est l'intervalle $[\mathit{lower}+\delta, \mathit{upper}+\delta]$. Créez une fonction pour calculer un décalage.
La fusion de deux intervalles $\mathit{inter}_1$ et $\mathit{inter}_2$est le plus petit intervalle contenant $\mathit{inter}_1$ et $\mathit{inter}_2$. Sa borne inférieure est le minimum des deux bornes inférieures, et sa borne supérieure est le maximum des deux bornes supérieures. Écrivez une fonction pour la fusion.
L'écart des intervalles $[\mathit{lower}_1, \mathit{upper}_1]$ et $[\mathit{lower}_2, \mathit{upper}_2]$ est $\mathit{lower}_2 - \mathit{upper}_1$. Ajoutez la fonction calculant l'écart de deux intervalles.
Ceci termine le fichier interval.ml. Ajoutez un fichier d'interface interval.mli exportant toutes les valeurs définies.
La suite se passe dans le fichier reingoldTilford.ml, qui va donc contenir l'algorithme de positionnement des nœuds.
Les dessins d'arbres que nous allons faire respecterons la règle : tous les nœuds d'une même profondeur dans l'arbre sont placés avec la même ordonnée (c'est-à-dire sur une ligne horizontale). Pour encoder l'espace pris par le dessin d'un arbre dans le plan, il suffit donc de garder pour chaque niveau de profondeur, l'intervalle entre le nœud le plus à gauche et le nœud le plus à droite.
Par exemple, pour l'arbre ci-contre, l'encodage est donné par :
| profondeur | intervalle |
|---|---|
| 0 | $[0,0]$ |
| 1 | $[-1,1]$ |
| 2 | $[-3,1]$ |
| 3 | $[-2,2]$ |
En première approche, nous pourrions donc poser le type des niveaux d'un arbre, donnant un intervalle pour chaque niveau de profondeur, par :
Les principales opérations que nous devrons faire sont :
Or, pour des raisons d'efficacité, nous ne voulons pas calculer ces opérations, sauf si nécessaire. Du coup nous allons utiliser une astuce, consistant à introduire dans le type des niveaux un constructeur pour le décalage (Shift) et un constructeur pour la fusion (Merge) (en plus des constructeurs de listes (Nothing et Interval), soit 4 constructeurs en tout), qui permettent de représenter sans les calculer un décalage des niveaux ou une fusion de deux listes de niveaux, sans les calculer.
Recopiez ce type inductif à 4 constructeurs pour les listes de niveaux.
Un des avantages est que le décalage d'une liste de niveaux, ou la fusion de deux listes de niveaux, sont des opérations en temps constant : il suffit d'appeler le constructeur avec les arguments, ce qui construit la valeur sans rien calculer. En revanche, observer la liste, c'est-à-dire récupérer le premier intervalle de la liste, et une représentation des autres intervalles de la liste, va devenir une opération plus complexe. En effet, si le premier élément est une fusion ou un décalage, il va falloir appliquer cette opération pour obtenir un intervalle.
Pour cela, la fonction principale va être :
Ainsi, en utilisant match observe_levels levels with, nous retomberons sur un filtrage par motif qui ressemblera à celui d'une liste (soit la liste est vide, soit elle se compose d'une tête et d'une queue). Il y a plusieurs cas.
Cas 1 . La liste de niveaux commence par une fusion. Dans ce cas, il suffit d'observer chacun des deux termes de la fusion, et si nécessaire fusionner les têtes avec merge et les queues avec le constructeur adéquat. Créez d'abord la fonction suivante :
Elle calcule la fusion des premiers intervalles, et utilise le constructeur adapté pour fusionner les listes de niveaux.
Utilisez ensuite merge_levels pour faire le premier cas dans observe_levels. On fait récursivement l'observation des premiers termes de chaque liste, puis on appelle merge_levels pour en faire une seule liste. Comme observe_levels retourne une option, on ne peut pas utiliser directement merge_levels, mais on s'en sort avec le combinateur Option.merge (voir la documentation) !
Cas 2 . La liste de niveaux commence par deux décalages successifs. Nous les remplaçons par un seul décalage d'une valeur égale à la somme des deux. Puis nous observons récursivement cette nouvelle liste de niveaux. Cette opération est cruciale pour rendre l'algorithme efficace.
Cas 3 . La liste de niveaux commence par un décalage. Dans ce cas, on observe les niveaux à décaler, puis on décale la tête avec Interval.shift, et la queue avec le constructeur de décalage. Programmez d'abord la fonction correspondante :
De nouveau, il faut utiliser un combinateur d'Option pour utiliser shift_levels dans observe_levels.
Cas 4 . La liste de niveaux commence par un constructeur de liste, l'observation est alors triviale.
Finalisez et testez la fonction observe_levels.
L'algorithme de Reingold et Tilford de placement des nœuds procède de façon récursive, du bas vers le haut de l'arbre. Étant donné un placement pour les deux sous-arbres d'un nœud $n$, les deux sous-arbres sont placés côte-à-cote avec leurs racines à la même ordonnée. Ils sont placés le plus proche possible, de sorte que tout nœud du sous-arbre gauche aient une abscisse au moins inférieur de 2 à tout nœud du même niveau dans le sous-arbre droit. Enfin, $n$ est placé une ordonnée au dessus et à mi-chemin horizontalement des deux racines.
Le cœur de l'algorithme est de calculer à quelle distance doivent être les deux racines des sous-arbres l'une de l'autre. Si nous utilisions des listes, l'algorithme se décrirait approximativement par :
Autrement dit, on calcule niveau par niveau l'écart nécessaire, et on garde le maximum (mais au moins 2).
Puisque nous n'avons pas utilisé les listes, il nous faut réécrire cet algorithme via une récursion. Une version simplifiée aurait pour type :
et calculerait récursivement l'écart entre les queues de deux listes, l'écart nécessaire entre les têtes, et retournerait le maximum des deux. Dans un premier temps, programmez cette fonction.
Dans cette première version, pour combiner les deux listes, de nombreux appels à observe_levels ont été faits, qui ont potentiellement considérablement simplifié les deux listes de niveaux, en repoussant les Shift et Merge vers la fin des deux listes. Or, nous n'en avons gardé aucune trace, et donc tout le calcul devra être refait par la suite si nécessaire. Vous pouvez améliorer cela de plusieurs façons, en voici deux (implémentez celle de votre choix) :
Modifier compute_necessary_gap pour qu'elle retourne aussi les deux listes de niveaux simplifiées. Son type sera alors :
Avant de calculer l'écart avec la version naïve de compute_necessary_gap, on peut forcer la simplification des deux listes de sorte que la plus courte des deux soient entièrement simplifiées. Pour cela, on crée une fonction simplify2 qui prend deux listes en arguments, et les observe récursivement jusqu'à observer que l'une est vide. On retourne les listes de niveaux simplifiées.
D'après la description de l'algorithme, l'information nécessaire est de connaître pour chaque nœud, la distance horizontale entre ses deux enfants. Une fois connue cette information, il sera possible de construire l'arbre en partant de la racine. Dans un premier temps, nous devons donc calculer pour chaque nœud, cette distance horizontale : le décalage de ce nœud. Nous le faisons par un algorithme récursif (de type bottom-up).
Pour calculer le décalage d'un nœud, il faut commencer par construire la liste des niveaux de ces deux enfants, et par la même occasion leurs décalages. Ceci s'effectue par récursion. Ensuite, compute_necessary_gap nous donne le décalage pour la racine. Enfin, pour la récursion, il faut aussi construire la liste de niveaux du nœud, en décalant (avec Shift) les deux listes des sous-arbres par la moitié du décalage de la racine, et en les fusionnant (avec Merge), et en ajoutant devant l'intervalle pour le niveau de la racine : $[0,0]$.
Écrivez la fonction correspondante, qui retourne l'arbre annoté des décalages de chaque nœuds, et la liste des niveaux de l'arbre :
Le plus dur est fait. Nous plaçons maintenant la racine en position $(0,0)$, puis par une récursion, descendons dans l'arbre annoté pour placer les nœuds des sous-arbres.
Écrivez la fonction de placement des nœuds depuis un arbre annoté :
La racine d'un sous-arbre d'un nœud $n$ a son ordonnée inférieur de 1 par rapport à celle de $n$, et son abscisse à distance $\mathit{gap}/2$ de celle de $n$, avec $\mathit{gap}$ le décalage encodé dans l'arbre annoté.
Combinez les éléments pour obtenir une fonction :
Puis utilisez ExportSvg et les fonctions de BinTree pour obtenir l'image d'arbres. Essayez avec les arbres complets, les chemins, les chenilles. Puis utilisez le générateur aléatoire :
Vous pouvez ensuite ajouter des fonctions pour calculer automatiquement la vue nécessaire pour afficher l'arbre en entier. Pour cela, on utilise fold pour calculer les vecteurs des coins sud-ouest et nord-est, en utilisant des opérateurs de minimum et maximum coordonnée-par-coordonnée.
Ajoutez des générateurs d'arbres aléatoires plus sophistiqués. Celui que nous avons utilisé construit des arbres qui sont toujours assez compacts. Il serait intéressant de construire des arbres ayant tendance à être plus profond. Par exemple, on pourrait choisir entre créer une bifurcation avec deux sous-arbres aléatoires, créer un chemin droit suivi d'un arbre aléatoire, et créer un chemin gauche suivi d'un arbre aléatoire. On peut faire ça avec QCheck, en utilisant des générateurs travaillant avec une taille (voir la documentation, ainsi que le générateur fourni)
Sur des arbres très profonds, l'algorithme va échouer avec un Stack overflow. La raison est que nous utilisons un algorithme récursif. Pour éviter le débordement de pile, il faut que les appels récursifs soient le dernier calcul de la fonction, on parle alors de récursion terminale. Peut-on réécrire l'algorithme en forme récursive terminale ?
L'algorithme utilise une fonction récursive montante, calculant depuis les feuilles vers la racine, et une fonction récursive descendante, partant de la racine et propageant vers les feuilles. Pouvez-vous imaginer d'autres fonctions sur les arbres fonctionnant de ces deux manières ? Pouvez-vous capturer le schéma de récurrence de ces fonctions en proposant deux autres fonctionnelles sur les arbres, puis les utiliser pour réécrire l'algorithme ?
Nous avons utilisé ici une technique pour ne pas effectuer de calculs inutiles, en manipulant une représentation adaptée des listes d'intervalles. Une solution plus simple est d'adopter des listes paresseuses en utilisant le module Lazy, qui permet de faire de l'évaluation paresseuse. Nous ferons bientôt un TP sur ce sujet, et vous pourrez alors revenir sur ce TP pour le simplifier.
