Treemap

Répartition : Julien BERSAUTER (GROUPE 3, sujet 18)

I - Introduction

Nous ne pouvons introduire la notion de TreeMap autrement qu'en donnant définition concrète d'un TreeMap. Avant toutes choses, pour comprendre ces notions, il faudra être familier avec les notions d'arbres et de graphes.

Définition : Le TreeMap est un Arbre (tree) qu'on agence sur un plan (map) en 2D ou 3D via des formes qui sont dans la plupart des cas rectangulaires pour simplifier la visualisation de données.

Le TreeMap utilise la structure d'Arbre. Cet arbre possède une spécificité : Chaque nœud possède un poids qui est égal à la somme de ses feuilles. Les feuilles représentent le contenu (y compris le contenu vide) et les autres nœuds, le conteneur.

Définition d'un Arbre : C'est un graphe qui est à la fois connexe et acyclique. Chaque nœud est relié à ses fils, et peut posséder un poids.

Nous nous intéresserons ici aux TreeMap, sur un plan en 2 Dimensions, où les données sont représentés par des formes rectangulaires.

Cette représentation a été inventée à la base pour représenter une arborescence de fichier sur un disque dur et pour trouver les plus gros fichiers rapidement. Il existe évidemment d’autres applications avec cette représentation :

  • Représenter l’occupation de plusieurs bâtiments d’entrepôt (avec des feuilles représentant les espaces vides ou occupés).
  • Un calendrier, avec, pour chaque jour, une taille plus ou moins élevée en fonction de l’importance des tâches à effectuer pendant la journée.
  • Représenter un budget ordonné par catégorie.
  • Les données d’un sondage ou d’une élection, par zone géographique.
  • Une hiérarchie au sein d'une entreprise
  • ...

Comment afficher des données efficacement dans le plan ?

EN UTILISANT DES ALGORITHMES !

La principale difficulté pour les TreeMaps est donc de choisir (et de programmer...) un algorithme pour afficher, de manière efficace, esthétique, triée et qui conserve au mieux les proportions de chaque données.

1 - Algorithmes et leurs propriétés

Pour représenter ces données sur un plan, il nous faudra utiliser des algorithmes. Il existe plusieurs algorithmes, qui ont tous des avantages différents, certains représentent l'avantage d'être esthétique et/ou de conserver l'ordre et/ou de respecter les proportions. Il est possible de combiner plusieurs algorithme à la fois en fonction de l'étage.

Définition - Stabilité d'un Algorithme : Un algorithme est dit stable s'il conserve l'ordre de ses éléments.

Algorithme Conservation de l’ordre Respect des proportions Stabilité
Arbre Binaire (BinaryTree) Partiel Important Stable
Carte proportionnelle mixtes (Mixed Treemaps) Conservé Faible Stable
Ordonnancé (Ordered) Partiel Moyen Moyenne
Par eminçage (Slice And Dice) Conservé Très Important Stable
Mise au carré (Squarified) Non conservé Faible Moyen
En Bandes (Strip) Conservé Moyen Moyen

(Source du tableau : https://fr.wikipedia.org/wiki/Treemap )

On remarquera que l’algorithme Slice And Dice produit le résultat le plus intéressant (Tri stable, Ordre conservé, respect des proportions très important) mais il peut présenter un désavantage esthétique.

En effet, il affiche des bandes verticales et non des rectangles bien agencés.

Nous allons donc voir dans la prochaine section cet algorithme.

Algorithmes Slice and Dice

Exemple d’un algorithme en pseudo-code pour un affichage Slice and Dice, utilisant le parcours en profondeur d'un arbre, dont chaque nœud contient une liste de ses fils, ainsi que son poids.

Treemap (Arbre a, Entier pixel){
// Arbre : Arbre.racine retourne le nœud RACINE
// Nœud : Nœud.poids retourne le poids du nœud
// Nœud.liste contient la liste des fils de nœud

	Noeud n := a.racine
	Treemap_rec (n,0,100,pixel)
}


Treemap_rec (Nœud n, Flottant début, Flottant fin, Entier pixel){
// Flottant début : délimite le début du rectangle où l'on dessine actuellement
// Flottant fin : Délimite la fin du rectangle où l'on dessine actuellement
// Entier pixel : taille du rectangle de base

	Flottant x := début;
	Pour chaque fils f contenu dans n.liste faire :
		Flottant arrivée := arrondir(f.poids/n.poids)
		Dessiner(arrivée*(fin/100)*pixel)
		Treemap_rec(f, x, arrivée*n.poids,pixel)
		x := x+arrivée
	Fin Pour chaque

/* La boucle est assez simple :
 * Pour chaque fils du nœud n
 * - On initialise une variable arrivée qui déterminera l'espace      
 *   (en ratio) occupé par le fils f
 * - On dessine dans la zone où est censé s'arrêter le sous-rectangle f
 * - On appel récursivement Treemap_rec sur f, auquel on modifie début et
 * - fin pour que ça corresponde à la zone occupée par f.
 * - On incrémente x de la valeur d'arrivée de f.
 */

}

Arrondir () // Arrondit à la 3eme décimale (inférieure)
Dessiner () // Dessine dans la zone d'affichage actuel une barre verticale au pixel indiqué

Le principe de cet algorithme est simple, on prend le nœud principal, on dessine un rectangle, puis on subdivise ce rectangle proportionnellement au poids de chaque fils. Et ainsi de suite jusqu'à ce que l'arbre soit entièrement parcouru.

L'algorithme conserve parfaitement les proportions, c'est-à-dire que chaque nœud fils prend exactement (taille du père / taille du fils) en espace. Comme l'algorithme est récursif, la propriété est étendu à celle de tous ses fils.

Cet algorithme conserve l'ordre, c'est-à-dire que les nœuds sont toujours affichés dans le même ordre de parcours.

Appliquons maintenant cet algorithme sur un exemple concret.

On appel l'algorithme TreeMap slice-and-dice avec l'arbre ci-dessous, et un entier pixel de taille 1000.

Ordre de parcours de l'arbre numéroté de 1 à 10.
Arbre avec le poids de chaque nœuds.

L'algorithme devrait afficher un plan qui n'est pas très esthétique, ressemblant à ceci :

Le cadre représente le noeud principal.
De gauche à droite :
-Le noeud 2, qui lui même contient les noeuds 3 et 4
-Le noeud 5 qui contient les noeuds 6 et 7
-Le noeud 8 qui contient le noeud 9 et 10

Exercice 1

En réalité, il existe une multitude d'algorithme pour représenter un TreeMap. Nous proposons donc de faire notre propre algorithme, inspiré de "slice and dice".

  1. Écrire deux fonctions qui prennent en entrée un nœud et qui découpent respectivement le plan de manière horizontale et verticale, en fonction de leurs fils directs, puis s'appellent l'un et l'autre de manière récursive sur chaque fils de manière à obtenir un découpage qui alterne entre les deux méthodes.
  2. Finalement, définir un algorithme qui prend en entrée un arbre et qui dessine le TreeMap en s'inspirant des fonctions de (1).
  3. Les proportions sont-elles respectées avec cette méthode ? Et l'ordre?
  4. Appliquez cet algorithme sur le TreeMap vu plus haut et dessinez-le. Est-ce plus lisible ? Essayez avec des arbres plus longs et/ou avec plus de feuilles.

Un autre algorithme

On se propose de faire un algorithme "TreeMap Ordonné".

Le TreeMap_Ordonné_Rec prendra une liste de nœuds (indice 0 à n) d'un arbre et un rectangle R.

Le TreeMap ordonné utilise un pivot (qu'on peut choisir de différentes manières) pour arranger les éléments dans le plan.

Dans notre exemple, le pivot sera l'élément de poids le plus élevé de la liste.

S'il y au plus 4 éléments dans la liste, on applique la fonction disposer() qui elle-même appellera TreeMap_Ordonné_Rec à la fin, et qui sélectionnera une disposition parmi les suivantes :

On découpe un rectangle en 4 zone (R1,R2,R3,Rp), auquel on ajoutera une liste d'éléments chacun (respectivement L1,L2,L3,Pivot)

-L1 contiendra tous les éléments de L d'indice inférieur à Pivot.
-L2 tous le reste.
-L3 sera vide à la base.
-Pivot sera une liste d'un seul élément.

En fonction du poids de chaque zone R1, R2, R3 et Rp, on les redimensionne.


Ensuite on ajoute de R2 à R3 les éléments les plus gros de R2 tant que ça rapproche le ratio hauteur/largeur du rectangle Rp à 1 (le plus proche d'un carré donc), qui est caractérisé dans l'algo par la fonction Condition() .

Ensuite on redimensionne le tout.

On utilisera un modèle de dispositions par défaut

Source : http://www.cs.umd.edu/hcil/trs/2001-18/2001-18.html
NB : Si la largeur > hauteur, alors il faudra le découper comme s'il était renversé.

On donnera cet algorithme :

TreeMap_Ordonné(R, Racine)
  début
    L = Liste des fils directes de Racine
    TreeMap_Ordonné_rec(L,R)
  fin

TreeMap_Ordonné_rec (L, R)
//Rectangle R
//Liste L
début
Si (Liste <= 4) faire
   Disposer(L)
Sinon 
      Pivot := L'élément de poids le plus élevés dans L
      Découper(R)
      L1 := Tous les éléments de L d'indice inférieur à Pivot
      L2 := Tous les éléments de L d'indice supérieur à Pivot
      L3 := Vide
      Redimensionner(R)
      TANT QUE (Condition()) faire
       Début TANT QUE
           ajouter l'élément le plus grand de R2 à R3;
           Redimensionner(R)
      Fin TANT QUE
      TreeMap_Ordonné_rec(R1,liste des fils de L1)
      TreeMap_Ordonné_rec(R2,liste des fils de L2)
      TreeMap_Ordonné_rec(R3,liste des fils de L3)
      TreeMap_Ordonné_rec(Rp,liste des fils de Pivot)
fin

Exercice 2

1) A quel algorithme déjà connu vous fait penser cet algorithme ? Rappelez sa complexité. Détaillez le nombre d'opérations nécessaires.
2) Programmez les fonctions Redimensionner, Disposer, et Condition.
3) Quels choix de découpages avez-vous fait ?
4) Prouvez que cet algorithme donne de bonnes proportions.
5) Pourquoi est-ce que l'algorithme conserve l'ordre des éléments ?

Bibliographie :
http://www.cs.umd.edu/hcil/trs/2001-18/2001-18.html https://en.wikipedia.org/wiki/Treemapping
https://fr.wikipedia.org/wiki/Treemap

0 Cliquer pour recommander cet article