Dans ce TP, nous allons utiliser les types algébriques, d'abord pour définir des arbres binaires génériques, puis pour coder un algorithme de placement des nœuds d'un arbre binaire en vue de le dessiner.
Rappellons le type des options (prédéfini dans Pervasive), qui permettent d'encoder la présence ou l'absence d'une valeur :
Les fonctions suivantes pourront peut-être vous être utiles (mais ne sont pas obligatoires) :
Proposer un type union pour encoder les arbres binaires, paramêtré par le type des nœuds.
Écrire plusieurs fonctions, qui étant donné un entier $n$, construisent les arbres suivants. Tous les nœuds contiendront une valeur de type unit.
Écrire une fonction calculant l'image miroir d'un arbre, comme illustré par le dessin ci-dessous.
 |  |
Écrire la fonction calculant la hauteur d'un arbre binaire.
Écrire la fonction map des arbres binaires. map ~f construit une image de l'arbre en remplaçant chaque nœud par son image par la fonction f.
Écrire une fonction fold des arbres binaires. Elle doit correspondre à faire un List.fold_left sur une liste des nœuds de l'arbre.
Écrire une fonction retournant une liste de nœuds d'un arbre binaire, en ordre préfixe. Pour cela, on utilisera une fonction annexe insert_nodes_of tree accu, ajoutant tous les nœuds de tree dans l'accumulateur accu.
Écrire une fonction retournant la liste des paires (parent,enfant) d'un arbre binaire. Utiliser une fonction annexe insert_edges_of tree ?father accu, prenant aussi un arbre et un accumulateur en argument, ainsi qu'un argument optionnel précisant le père du nœud racine de tree, s'il existe.
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 codé par la donnée de ses deux extrémités $\mathit{lower}$ et $\mathit{upper}$, qui sont des flottants.
Proposer un type produit pour les intervalles.
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]$. Proposer 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. Écrire une fonction pour la fusion.
L'écart des intervalles $[\mathit{lower}_1, \mathit{upper}_1]$ et $[\mathit{lower}_1, \mathit{upper}_1]$ est $\mathit{lower}_2 - \mathit{upper}_1$. Écrire la fonction calculant l'écart de deux intervalles.
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 coder explicitement un décalage des niveaux ou une fusion de deux listes de niveaux, sans les calculer.
Proposer un 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. En revanche, observer la liste, c'est-à-dire récupérer la tête et la queue de la liste, va devenir une opération plus complexe.
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. 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. Coder la fonction correspondante :
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 cette nouvelle liste de niveaux.
Cas 3 . La liste de niveaux commence par un décalage. Dans ce cas, on observe le terme du décalage, puis on décale la tête avec shift, et la queue avec le constructeur de décalage. Coder la fonction correspondante :
Cas 4 . La liste de niveaux commence par un constructeur de liste, il n'y a alors rien à faire pour l'observation.
Finalement, coder 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 est 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, coder cette fonction.
Dans cette première version, pour combiner les deux listes, de nombreux appels à observe_levels ont été fait, 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. Modifier compute_necessary_gap pour qu'elle retourne aussi les deux listes de niveaux simplifiées. Son type sera alors :
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 fils. 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 fils, 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 niveau 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]$.
Écrire 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.
Écrire 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é.
Combiner les éléments pour obtenir une fonction :
Il devrait maintenant être facile de créer une image d'un arbre binaire. Nous proposons d'utiliser au choix la librairie Graphics, ou si vous l'avez sur votre machine la librairie Vg (utilisée pour réaliser les figures de cette page).
Dans le toplevel, charger la librairie et ouvrir une fenêtre avec les dimensions souhaitées.
Utiliser Graphics.fill_circle pour écrire une fonction dessinant un nœud draw_node pixel_of_position position. pixel_of_position sera définie plus tard.
Utiliser Graphics.moveto et Graphics.lineto pour écrire une fonction dessinant une arête, avec le même format que draw_node.
Utiliser la fonction fold des arbres binaires pour calculer les abscisses minimum et maximum, les ordonnées minimum et maximum, d'un arbre binaire dont les nœuds sont des positions.
Compléter la fonction de dessin, en utilisant List.iter sur les listes de nœuds et d'arêtes :
Créer un fichier .merlin dans le répertoire courant, contenant :
Sous emacs, dans le menu Merlin, sélectionner Restart merlin.
Sous emacs, fermer le toplevel en tapant exit 0;;dedans. Relancer le toplevel en ré-évaluant le buffer, mais cette fois utiliser l'exécutable utop.
Dans le toplevel, exécuter :
Vg est basé sur le principe du découper-coller : on découpe des formes dans des feuilles de papier colorées, puis on les colle sur une image. Il y a donc un module pour le découpage Vg.P qui se fait en définissant le chemin (P pour path) par lequel passe la paire de ciseaux. Et il y a un module pour le collage Vg.I (I pour image).
Vg s'appuie sur Gg pour les calculs vectoriels et les couleurs. Nous utiliserons principalement Gg.V2 pour les vecteurs à deux dimensions, et Gg.Color pour les couleurs.
Pour dessiner un nœud, on part d'un chemin vide, puis on crée une forme de cercle, que l'on colle à l'image. On utilise les fonctions suivantes :
Créer un chemin circulaire, le couper dans une feuille noire, puis le coller sur une image donnée en argument :
Utiliser les mêmes principes pour le dessin d'une arête. Dans ce cas, notons que nous ne voulons pas découper l'intérieur d'une forme, mais juste son contour. Pour cela, il faut donner un argument supplémentaire à Vg.I.cut.
Écrire la fonction :
Comme avec Graphics, donner des fonctions pour récupérer les coordonnées minimum et maximum des nœuds de l'arbre.
En déduire une fonction calculant la diagonale et le centre du rectangle d'un arbre (ajouter une marge de 1 de chaque côté).
Nous venons de voir comment calculer le plus petit rectangle contenant l'arbre, mais nous voulons afficher une image avec une largeur et une hauteur donnée, et le ratio largeur/hauteur n'est pas nécessairement le même que celui du rectangle. Nous le corrigeons ainsi :
Une image affichable se compose de l'image elle-même, de la taille désirée exprimée par un vecteur Gg.V2.t en millimètre, et de la vue calculée à la question précédente. Écrire la fonction créant une telle image depuis un arbre et une spécification de la taille de l'image voulue.
À partir de là, l'image peut être affichée dans un canvas html, dans un fichier pdf ou dans un fichier svg. Nous choisissons la dernière option. On utilise le code suivant (à modifier légèrement) :
render_image prend un titre pour l'image, un descripteur de fichier en sortie out_channel : Pervasive.out_channel, et l'image, et écrit l'image dans le descripteur.
Nous le complétons avec l'ouverture et la fermeture d'un fichier :
Pour finir, voici trois fonctions pour générer des arbres binaires aléatoires.
Le troisième générateur permet de créer des arbres plus profonds. Avec un grand nombre de nœuds, votre algorithme risque de provoquer un stack overflow. Pour les arbres de hauteur 100.0 00 ou plus, il faudrait réécrire votre algorithme en utilisant ContinuationMonad pour toutes les récursions, comme ci-dessous.
Et une fonction pour chronométrer votre algorithme. Quel comportement asymptotique semble-t-il avoir ?(gare aux stack overflow sur de trop gros arbres).
