Callcc/Guyslain/Teaching/ProgFonc/TP2018/tp6-algorithme-de-reingold-tilford

Version & licenses
Creative Commons License
  1. {`author "Guyslain Naves"}
  2. {`date "Janvier 2018"}
  3. {`windowtitle "Programmation Fonctionnelle, TP6"}
  4. {`frametitle "Programmation Fonctionnelle, TP6 : Algorithme de Reingold et Tilford."}
  5. {`menu "progfonc"}
  6. {`leftpicture af://guyslain/images/Teaching/ProgFonc/ReingoldTilford/random_tree_v4_1.svg}


  7. Cet algorithme est la suite du {link
  8. af://callcc/Guyslain/Teaching/ProgFonc/TP2018/tp5-dessin-d-arbre-binaire
  9. TP 5} sur les arbres binaires. Pour mettre tout le monde au même
  10. niveau, voici {link af://guyslain/teaching/sources/TP6ReingoldTilford.zip
  11. une correction du TP}.

  12. En particulier, le module des arbres binaires contient une fonction de
  13. dessin. Le fichier {verb {:trivial_embedding:}} peut être compilé en
  14. exécutable : il faut avant de l'exécuter créer un sous-repertoire
  15. {verb {:pic:}} dans lequel il mettra un dessin naïf de l'arbre
  16. complet.


  17. {section 3 Intervalles.}

  18. Pour l'algorithme de placement des nœuds, il va être capital de
  19. représenter l'espace horizontal pris par un arbre, sous la forme d'un
  20. intervalle de la ligne des nombres réels. Un intervalle
  21. $[\mathit{lower},\mathit{upper}]$, avec $\mathit{lower} \leq
  22. \mathit{upper}$, est représenté par la donnée de ses deux extrémités
  23. $\mathit{lower}$ et $\mathit{upper}$, qui sont des flottants.
  24. Il y a aussi un intervalle particulier, l'intervalle vide.

  25. {section 4 Type des intervalles.}

  26. Proposez un type pour les intervalles. Les fonctions pour ce
  27. type seront placées dans un fichier {verb {:interval.ml:}}. Ajoutez
  28. aussi une fonction de création d'un intervalle, et deux accesseurs.

  29. {code {`language "ocaml"} {:
  30. type t

  31. val empty : t
  32. val v : float -> float -> t
  33. val (--) : float -> float -> t (** infix for [v] *)

  34. val get_lower : t -> float option
  35. val get_upper : t -> float option
  36. :}}


  37. Nous continuons avec plusieurs fonctions pour manipuler des intervalles.


  38. {section 4 Décaler un intervalle}


  39. Le décalage de l'intervalle $[\mathit{lower},\mathit{upper}]$ par un
  40. flottant $\delta$ est l'intervalle $[\mathit{lower}+\delta,
  41. \mathit{upper}+\delta]$. Créez une fonction pour calculer un décalage.

  42. {code {`language "ocaml"} {:
  43. val shift : float -> t -> t
  44. :}}


  45. {section 4 Fusion de deux intervalles}

  46. La fusion de deux intervalles $\mathit{inter}_1$ et $\mathit{inter}_2$
  47. est le plus petit intervalle contenant $\mathit{inter}_1$ et
  48. $\mathit{inter}_2$. Sa borne inférieure est le minimum des deux bornes
  49. inférieures, et sa borne supérieure est le maximum des deux bornes
  50. supérieures. Écrivez une fonction pour la fusion.

  51. {code {`language "ocaml"} {:
  52. val merge : t -> t -> t (** Monoid with neutral [empty] *)
  53. :}}


  54. {section 4 Écart de deux intervalles}

  55. L'écart des intervalles $[\mathit{lower}_1, \mathit{upper}_1]$ et
  56. $[\mathit{lower}_2, \mathit{upper}_2]$ est $\mathit{lower}_2 -
  57. \mathit{upper}_1$. Ajoutez la fonction calculant l'écart de deux intervalles.

  58. {code {`language} {:
  59. val gap : t -> t -> float option
  60. :}}

  61. Ceci termine le fichier {verb {:interval.ml:}}. Ajoutez un fichier
  62. d'interface {verb {:interval.mli:}} exportant toutes les valeurs définies.


  63. {section 3 Niveaux d'un arbre.}

  64. La suite se passe dans le fichier {verb {:reingoldTilford.ml:}}, qui
  65. va donc contenir l'algorithme de positionnement des nœuds.

  66. Les dessins d'arbres que nous allons faire respecterons la règle :
  67. tous les nœuds d'une même profondeur dans l'arbre sont placés avec la
  68. même ordonnée (c'est-à-dire sur une ligne horizontale). Pour encoder
  69. l'espace pris par le dessin d'un arbre dans le plan, il suffit donc de
  70. garder pour chaque niveau de profondeur, l'intervalle entre le nœud le
  71. plus à gauche et le nœud le plus à droite.

  72. {image af://guyslain/images/Teaching/ProgFonc/ReingoldTilford/random_8.svg
  73. {`tooltip "Un arbre quelconque"} {`height 200} {`width 200} {`left}
  74. Un arbre quelconque
  75. }
  76. {subframe
  77. Par exemple, pour l'arbre ci-contre, l'encodage est donné par :
  78. {array 5 2 {`head 1}
  79. profondeur intervalle
  80. 0 {$[0,0]$}
  81. 1 {$[-1,1]$}
  82. 2 {$[-3,1]$}
  83. 3 {$[-2,2]$}
  84. }
  85. }

  86. En première approche, nous pourrions donc poser le type des niveaux
  87. d'un arbre, donnant un intervalle pour chaque niveau de profondeur,
  88. par :

  89. {code {`language "ocaml"} {:
  90. (* Ne pas recopier ! *)
  91. type levels = interval list
  92. :}}

  93. Les principales opérations que nous devrons faire sont :
  94. - décaler tous les intervalles de la listes,
  95. - fusionner tous les intervalles de deux listes un-à-un,

  96. Or, pour des raisons d'efficacité, nous ne voulons pas calculer ces
  97. opérations, sauf si nécessaire. Du coup nous allons utiliser une
  98. astuce, consistant à introduire dans le type des niveaux un
  99. constructeur pour le décalage ({verb {:Shift:}}) et un constructeur
  100. pour la fusion ({verb {:Merge:}}) (en plus des constructeurs de listes
  101. ({verb {:Nothing:}} et {verb {:Interval:}}), soit 4 constructeurs en
  102. tout), qui permettent de représenter sans les calculer un décalage des
  103. niveaux ou une fusion de deux listes de niveaux, sans les calculer.

  104. {section 4 Type des niveaux.}

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

  106. {code {`language "ocaml"} {:
  107. type levels =
  108. | Merge of levels * levels
  109. | Shift of float * levels
  110. | Interval of Interval.t * levels
  111. | Nothing
  112. :}}


  113. {section 4 Observer une liste de niveaux.}

  114. Un des avantages est que le décalage d'une liste de niveaux, ou la
  115. fusion de deux listes de niveaux, sont des opérations en temps
  116. constant : il suffit d'appeler le constructeur avec les arguments, ce
  117. qui construit la valeur sans rien calculer. En revanche, observer la
  118. liste, c'est-à-dire récupérer le premier intervalle de la liste, et
  119. une représentation des autres intervalles de la liste, va devenir une
  120. opération plus complexe. En effet, si le premier élément est une
  121. fusion ou un décalage, il va falloir appliquer cette opération pour
  122. obtenir un intervalle.

  123. Pour cela, la fonction principale va être :
  124. {code {`language "ocaml"} {:
  125. val observe_levels : levels -> (interval * levels) option
  126. :}}

  127. Ainsi, en utilisant {verb {:match observe_levels levels with:}}, nous
  128. retomberons sur un filtrage par motif qui ressemblera à celui d'une
  129. liste (soit la liste est vide, soit elle se compose d'une tête et
  130. d'une queue). Il y a plusieurs cas.

  131. Cas 1. La liste de niveaux commence par une fusion. Dans ce cas, il
  132. suffit d'observer chacun des deux termes de la fusion, et si
  133. nécessaire fusionner les têtes avec {verb {:merge:}} et les queues
  134. avec le constructeur adéquat. Créez d'abord la fonction suivante :
  135. {code {`language "ocaml"} {:
  136. val merge_levels :
  137. (interval * levels) -> (interval * levels) -> (interval * levels)
  138. :}}
  139. Elle calcule la fusion des premiers intervalles, et utilise le
  140. constructeur adapté pour fusionner les listes de niveaux.

  141. Utilisez ensuite {verb {:merge_levels:}} pour faire le premier cas
  142. dans {verb {:observe_levels:}}. On fait récursivement l'observation
  143. des premiers termes de chaque liste, puis on appelle {verb
  144. {:merge_levels:}} pour en faire une seule liste. Comme {verb
  145. {:observe_levels:}} retourne une option, on ne peut pas utiliser
  146. directement {verb {:merge_levels:}}, mais on s'en sort avec le
  147. combinateur {verb {:Option.merge:}} (voir la documentation) !

  148. Cas 2. La liste de niveaux commence par deux décalages
  149. successifs. Nous les remplaçons par un seul décalage d'une valeur
  150. égale à la somme des deux. Puis nous observons récursivement cette
  151. nouvelle liste de niveaux. Cette opération est cruciale pour rendre
  152. l'algorithme efficace.

  153. Cas 3. La liste de niveaux commence par un décalage. Dans ce cas, on
  154. observe les niveaux à décaler, puis on décale la tête avec {verb
  155. {:Interval.shift:}}, et la queue avec le constructeur de
  156. décalage. Programmez d'abord la fonction correspondante :
  157. {code {`language "ocaml"} {:
  158. val shift_levels :
  159. delta:float
  160. -> (interval * levels)
  161. -> (interval * levels)
  162. :}}

  163. De nouveau, il faut utiliser un combinateur d'{verb {:Option:}} pour
  164. utiliser {verb {:shift_levels:}} dans {verb {:observe_levels:}}.

  165. Cas 4. La liste de niveaux commence par un constructeur de liste,
  166. l'observation est alors triviale.

  167. Finalisez et testez la fonction {verb {:observe_levels:}}.

  168. {section 3 Algorithme de Reingold et Tilford.}

  169. {section 4 Calcul de l'écart nécessaire entre deux listes de niveaux (I).}

  170. L'algorithme de Reingold et Tilford de placement des nœuds procède de
  171. façon récursive, du bas vers le haut de l'arbre. Étant donné un
  172. placement pour les deux sous-arbres d'un nœud $n$, les deux
  173. sous-arbres sont placés côte-à-cote avec leurs racines à la même
  174. ordonnée. Ils sont placés le plus proche possible, de sorte que tout
  175. nœud du sous-arbre gauche aient une abscisse au moins inférieur de 2 à
  176. tout nœud du même niveau dans le sous-arbre droit. Enfin, $n$ est
  177. placé une ordonnée au dessus et à mi-chemin horizontalement des deux
  178. racines.

  179. Le cœur de l'algorithme est de calculer à quelle distance doivent être
  180. les deux racines des sous-arbres l'une de l'autre. Si nous utilisions
  181. des listes, l'algorithme se décrirait approximativement par :
  182. {code {`language "ocaml"} {:
  183. (* first line slightly incorrect: lengths may be distinct. *)
  184. List.combine left_levels right_levels
  185. |> List.map (fun (interval1,interval2) -> 2. -. gap interval1 interval2)
  186. |> List.fold_left max 2.
  187. :}}

  188. Autrement dit, on calcule niveau par niveau l'écart nécessaire, et on
  189. garde le maximum (mais au moins 2).

  190. Puisque nous n'avons pas utilisé les listes, il nous faut réécrire cet
  191. algorithme via une récursion. Une version simplifiée aurait pour type :

  192. {code {`language "ocaml"} {:
  193. val compute_necessary_gap : levels -> levels -> float
  194. :}}

  195. et calculerait récursivement l'écart entre les queues de deux listes,
  196. l'écart nécessaire entre les têtes, et retournerait le maximum des
  197. deux. Dans un premier temps, programmez cette fonction.

  198. {section 4 Calcul de l'écart nécessaire entre deux listes de niveaux (II).}

  199. Dans cette première version, pour combiner les deux listes, de
  200. nombreux appels à {verb {:observe_levels:}} ont été faits, qui ont
  201. potentiellement considérablement simplifié les deux listes de niveaux,
  202. en repoussant les {verb {:Shift:}} et {verb {:Merge:}} vers la fin des
  203. deux listes. Or, nous n'en avons gardé aucune trace, et donc tout le
  204. calcul devra être refait par la suite si nécessaire. Vous pouvez
  205. améliorer cela de plusieurs façons, en voici deux (implémentez celle
  206. de votre choix) :

  207. + {subframe Modifier {verb
  208. {:compute_necessary_gap:}} pour qu'elle retourne aussi les deux listes
  209. de niveaux simplifiées. Son type sera alors :

  210. {code {`language "ocaml"} {:
  211. val compute_necessary_gap : levels -> levels -> (float * levels * levels)
  212. :}}
  213. }
  214. + {subframe Avant de calculer l'écart avec la version naïve de {verb
  215. {:compute_necessary_gap:}}, on peut forcer la simplification des deux
  216. listes de sorte que la plus courte des deux soient entièrement
  217. simplifiées. Pour cela, on crée une fonction {verb {:simplify2:}} qui
  218. prend deux listes en arguments, et les observe récursivement jusqu'à
  219. observer que l'une est vide. On retourne les listes de niveaux simplifiées.

  220. {code {`language "ocaml"} {:
  221. val simplify2 : levels -> levels -> levels * levels
  222. :}}
  223. }





  224. {section 4 Annoter l'arbre avec les décalages nécessaires.}

  225. D'après la description de l'algorithme, l'information nécessaire est
  226. de connaître pour chaque nœud, la distance horizontale entre ses deux
  227. enfants. Une fois connue cette information, il sera possible de
  228. construire l'arbre en partant de la racine. Dans un premier temps,
  229. nous devons donc calculer pour chaque nœud, cette distance horizontale
  230. : le décalage de ce nœud. Nous le faisons par un algorithme récursif
  231. (de type {emph bottom-up}).

  232. Pour calculer le décalage d'un nœud, il faut commencer par construire
  233. la liste des niveaux de ces deux enfants, et par la même occasion leurs
  234. décalages. Ceci s'effectue par récursion. Ensuite, {verb
  235. {:compute_necessary_gap:}} nous donne le décalage pour la
  236. racine. Enfin, pour la récursion, il faut aussi construire la liste de
  237. niveaux du nœud, en décalant (avec {verb {:Shift:}}) les deux listes
  238. des sous-arbres par la moitié du décalage de la racine, et en les
  239. fusionnant (avec {verb {:Merge:}}), et en ajoutant devant l'intervalle
  240. pour le niveau de la racine : $[0,0]$.

  241. Écrivez la fonction correspondante, qui retourne l'arbre annoté des
  242. décalages de chaque nœuds, et la liste des niveaux de l'arbre :

  243. {code {`language "ocaml"} {:
  244. val annotate_with_offset : 'node bintree -> ('node * float) bintree * levels
  245. :}}


  246. {section 4 Annoter l'arbre avec les positions des nœuds.}

  247. Le plus dur est fait. Nous plaçons maintenant la racine en position
  248. $(0,0)$, puis par une récursion, descendons dans l'arbre annoté pour
  249. placer les nœuds des sous-arbres.

  250. Écrivez la fonction de placement des nœuds depuis un arbre annoté :
  251. {code {`language "ocaml"} {:
  252. val annotate_with_position :
  253. ~at:Gg.p2
  254. -> ('node * float) bintree
  255. -> ('node * Gg.p2) bintree
  256. :}}

  257. La racine d'un sous-arbre d'un nœud $n$ a son ordonnée inférieur de 1
  258. par rapport à celle de $n$, et son abscisse à distance
  259. $\mathit{gap}/2$ de celle de $n$, avec $\mathit{gap}$ le décalage
  260. encodé dans l'arbre annoté.

  261. {section 4 Finaliser l'algorithme.}

  262. Combinez les éléments pour obtenir une fonction :
  263. {code {`language "ocaml"} {:
  264. val layout : 'node bintree -> ('node * (float * float)) bintree
  265. :}}

  266. Puis utilisez {verb {:ExportSvg:}} et les fonctions de {verb
  267. {:BinTree:}} pour obtenir l'image d'arbres. Essayez avec les arbres
  268. complets, les chemins, les chenilles. Puis utilisez le générateur
  269. aléatoire :

  270. {code {`language "ocaml"} {:
  271. let get_random_tree =
  272. let open QCheck in
  273. ArbitraryTree.unit_tree.gen (Random.State.make_self_init ())
  274. :}}


  275. Vous pouvez ensuite ajouter des fonctions pour calculer
  276. automatiquement la vue nécessaire pour afficher l'arbre en
  277. entier. Pour cela, on utilise {verb {:fold:}} pour calculer les
  278. vecteurs des coins sud-ouest et nord-est, en utilisant des opérateurs
  279. de minimum et maximum coordonnée-par-coordonnée.


  280. {section 3 À vous de jouer...}

  281. Ajoutez des générateurs d'arbres aléatoires plus sophistiqués. Celui
  282. que nous avons utilisé construit des arbres qui sont toujours assez
  283. compacts. Il serait intéressant de construire des arbres ayant
  284. tendance à être plus profond. Par exemple, on pourrait choisir entre
  285. créer une bifurcation avec deux sous-arbres aléatoires, créer un
  286. chemin droit suivi d'un arbre aléatoire, et créer un chemin gauche
  287. suivi d'un arbre aléatoire. On peut faire ça avec {verb {:QCheck:}},
  288. en utilisant des générateurs travaillant avec une taille (voir la
  289. documentation, ainsi que le générateur fourni)

  290. Sur des arbres très profonds, l'algorithme va échouer avec un {verb
  291. {:Stack overflow:}}. La raison est que nous utilisons un algorithme
  292. récursif. Pour éviter le débordement de pile, il faut que les appels
  293. récursifs soient le dernier calcul de la fonction, on parle alors de
  294. récursion terminale. Peut-on réécrire l'algorithme en forme récursive
  295. terminale ?

  296. L'algorithme utilise une fonction récursive montante, calculant depuis
  297. les feuilles vers la racine, et une fonction récursive descendante,
  298. partant de la racine et propageant vers les feuilles. Pouvez-vous
  299. imaginer d'autres fonctions sur les arbres fonctionnant de ces deux
  300. manières ? Pouvez-vous capturer le schéma de récurrence de ces
  301. fonctions en proposant deux autres fonctionnelles sur les arbres, puis
  302. les utiliser pour réécrire l'algorithme ?

  303. Nous avons utilisé ici une technique pour ne pas effectuer de calculs
  304. inutiles, en manipulant une représentation adaptée des listes
  305. d'intervalles. Une solution plus simple est d'adopter des listes
  306. paresseuses en utilisant le module {verb {:Lazy:}}, qui permet de
  307. faire de l'évaluation paresseuse. Nous ferons bientôt un TP sur ce
  308. sujet, et vous pourrez alors revenir sur ce TP pour le simplifier.