Programmation Fonctionnelle, TP6

Htmligure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP6 : Algorithme de Reingold et Tilford.

Guyslain Naves

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.

Intervalles.

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.

Type des intervalles.

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.

  1. type t

  2. val empty : t
  3. val v : float -> float -> t
  4. val (--) : float -> float -> t (** infix for [v] *)

  5. val get_lower : t -> float option
  6. val get_upper : t -> float option

Nous continuons avec plusieurs fonctions pour manipuler des intervalles.

Décaler un intervalle

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.

  1. val shift : float -> t -> t

Fusion de deux intervalles

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.

  1. val merge : t -> t -> t (** Monoid with neutral [empty] *)

Écart de deux intervalles

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.

  1. val gap : t -> t -> float option

Ceci termine le fichier interval.ml. Ajoutez un fichier d'interface interval.mli exportant toutes les valeurs définies.

Niveaux d'un arbre.

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.

Un arbre quelconque

Par exemple, pour l'arbre ci-contre, l'encodage est donné par :

profondeurintervalle
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 :

  1. (* Ne pas recopier ! *)
  2. type levels = interval list

Les principales opérations que nous devrons faire sont :

  • décaler tous les intervalles de la listes,
  • fusionner tous les intervalles de deux listes un-à-un,

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.

Type des niveaux.

Recopiez ce type inductif à 4 constructeurs pour les listes de niveaux.

  1. type levels =
  2. | Merge of levels * levels
  3. | Shift of float * levels
  4. | Interval of Interval.t * levels
  5. | Nothing

Observer une liste 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 :

  1. val observe_levels : levels -> (interval * levels) option

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 :

  1. val merge_levels :
  2. (interval * levels) -> (interval * levels) -> (interval * levels)

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 :

  1. val shift_levels :
  2. delta:float
  3. -> (interval * levels)
  4. -> (interval * levels)

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.

Algorithme de Reingold et Tilford.

Calcul de l'écart nécessaire entre deux listes de niveaux (I).

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 :

  1. (* first line slightly incorrect: lengths may be distinct. *)
  2. List.combine left_levels right_levels
  3. |> List.map (fun (interval1,interval2) -> 2. -. gap interval1 interval2)
  4. |> List.fold_left max 2.

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 :

  1. val compute_necessary_gap : levels -> levels -> float

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.

Calcul de l'écart nécessaire entre deux listes de niveaux (II).

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) :

  1. Modifier compute_necessary_gap pour qu'elle retourne aussi les deux listes de niveaux simplifiées. Son type sera alors :

    1. val compute_necessary_gap : levels -> levels -> (float * levels * levels)
  2. 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.

    1. val simplify2 : levels -> levels -> levels * levels

Annoter l'arbre avec les décalages nécessaires.

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 :

  1. val annotate_with_offset : 'node bintree -> ('node * float) bintree * levels

Annoter l'arbre avec les positions des nœuds.

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é :

  1. val annotate_with_position :
  2. ~at:Gg.p2
  3. -> ('node * float) bintree
  4. -> ('node * Gg.p2) bintree

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é.

Finaliser l'algorithme.

Combinez les éléments pour obtenir une fonction :

  1. val layout : 'node bintree -> ('node * (float * float)) bintree

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 :

  1. let get_random_tree =
  2. let open QCheck in
  3. ArbitraryTree.unit_tree.gen (Random.State.make_self_init ())

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.

À vous de jouer...

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.