Projet
"Abraham engendra Isaac, Isaac engendra Jacob, ... "

Objectifs et modalités

Ce travail porte sur la mise en oeuvre de techniques de la programmation déclarative pour résoudre un problème plus conséquent que ceux proposés dans les séances d'exercices.

Les modalités sont les suivantes :

• Le travail est réalisé en groupe de deux étudiants (ou seul si ce n'est pas possible).

• Le travail est obligatoire et compte pour 5 points dans votre note finale.

• La date limite pour la remise est le mercredi 11 mai. L'évaluation se fera principalement par une interview avec l'assistant, pendant l'un des créneaux horaires à définir (vraissemblablement entre le 11 et le 13 mai).

  Par ailleurs, les fichiers seront envoyés par courrier électronique à jfallon@info.ucl.ac.be, si possible sous forme comprimée (format ZIP, par exemple).

• En cas de problème, envoyez un mail à jfallon@info.ucl.ac.be.

Concernant les programmes produits :

• Les programmes doivent être courts et simples. Préférez un programme clair et raisonnablement efficace à un programme rapide mais difficile à comprendre.

• Les programmes doivent être documentés.

• Les critères d'évaluation du travail sont la correction , la simplicité et la lisibilité des programmes.

Enoncé

Le travail consiste à implémenter un système de représentation d'arbres dans le modèle du calcul déclaratif vu au cours. La partie principale du travail consistera à implémenter l'algorithme assignant des positions aux noeuds de l'arbre. Le système prendra en entrée un fichier contenant des relations père-fils, de la forme : "père engendra fils1 et fils2 et fils3". Comme résultat, le système devra afficher à l'écran l'arbre dessiné. Certaines parties ont déjà été implémentées pour vous. Afin de les récupérer efficacement, il vous est proposé de "découper" le système de la façon suivante (les différentes étapes sont illustrées sur la figure qui suit les explications) :

1. Le fichier est passé à un parseur qui renvoie une liste de structure filiation(pere:Label fils:[Label1 Label2]), ayant comme champ le label du père (un atom), et une liste contenant les labels des fils (des atom également). Le parseur vous est fourni.
2. A partir de cette liste, il faut en extraire une structure d'arbre, c'est à dire créer une arborescence de structure tree(label:Label fils:[tree(...) tree(...) ...]).
3. On peut alors passer cette structure à l'algorithme qui va assigner une position aux noeuds de l'arbre. L'algorithme à implémenter est détaillé plus bas. Cet algorithme devra renvoyer une arborescence de structure posTree(label:Label xPos:XPos yPos:YPos fils:[...]).
4. Cette arborescence est alors passée à l'afficheur d'arbre. L'afficheur vous est également fourni.

L'algorithme de positionnement des noeuds d'un arbre

• Deux noeuds à la même profondeur doivent être séparés d'au moins une distance minimale donnée.
• Un parent doit être centré au-dessus de sa progéniture.
• Des arbres symétriques doivent être dessinés de façon symétrique.
• Deux arbres identiques doivent être dessinés identiquement.

Résultat de l'algorithme 1

Résultat de l'algorithme 2

L'algorithme 1

• L'algorithme fonctionne de manière récursive; en partant de l'hypothèse que tous les fils d'un noeud donné sont des arbres positionnés, il faut positionner ces fils les uns par rapport aux autres, et disposer le noeud parent au-dessus.
  
• Pour chaque noeud d'un arbre positioné, on enregistre :
  • sa position relative par rapport à son père;
  • L'"enveloppe" du sous-arbre dont ce noeud est racine. L'enveloppe décrit en fait l'envergure du sous-arbre. Pour cet algorithme, on va considérer des enveloppes rectangulaires (voir image)
  
  
• Ces données permettent de positionner tous les fils d'un noeud (afin qu'ils ne se superposent pas, et que tous les noeuds soient écartés au moins de la distance minimale requise). A partir de ces mêmes données, on peut calculer l'enveloppe du père, et faire en sorte que le père soit positionné au centre de sa progéniture!
  
  Pour l'algorithme 2, pensez à utiliser des enveloppes non plus rectangulaires, mais "en escalier", qui retient pour chaque arbre l'envergure à chaque niveau...
  
  

  Ressources techniques

  • Le parseur : Il fonctionne uniquement sous un environement Unix (Linux, Sun,...). Si vous souhaitez travailler sous Windows, vous pouvez tout de même tester votre code en créant une liste de structure filiation faite à la main.
    
    Pour l'utiliser sous Unix :
    • téléchargez ressources.tar et désarchivez le contenu de l'archive dans le dossier de vos sources.
    • Tapez alors la commande make dans une fenêtre de terminal, en étant dans le répertoire de vos sources. Cette commande permet de compiler les ressources en une fois.
    • Vous pouvez maintenant utiliser le module avec les commandes Oz suivantes :

      % charger le module (une fois)
      declare
      [BibleParser]={Module.link["BibleParser.ozf"]}
      ParseGenese=BibleParser.parseGenese
      
      % importer la liste de structure
      L={ParseGenese "CheminFichier.txt"}
      

    
    
    
  • L'afficheur d'arbres :

    % charger le module (une fois)
    declare
    [Displayer]={Module.link["http://www.info.ucl.ac.be/people/PVR/ds/LINF1251/projet/ressources/Displayer.ozf"]}
    Display=Displayer.display
    
    % afficher un arbre Arbre avec un FacteurDeZoom specifié (par exemple 80.0)
    {Display Arbre FacteurDeZoom}
    
    

  
  
  

  Bon travail !

  N'hésitez pas à prendre contact avec l'assistant (jfallon@info.ucl.ac.be) si vous rencontrez des problèmes.
  
  

  ---