CADCOM/MANUEL D'UTILISATION

REPRESENTATION DES GRAPHES


1) Introduction Nous nous intéressons ici aux méthodes habituelles de représentation de graphes de taille importante(plus de 100 noeuds),hierarchisés au préalable .

2) Algorithmes d'implantation(Layout) Tout algorithme a pour but de calculer la position des noeuds, la longueur des liaisons, d'éviter les collisions entre noeuds et le chevauchement des liaisons. Il doit également obéir à certaines règles comme: - Les structures de même forme doivent être disposées de la même maniere. - Les sommets de même profondeur doivent ètre au même niveau. - 2 exécutions d'un même algorithme doivent donner deux graphes identiques ou trés similaires - Le temps de calcul et d'affichage doit être court(les mises à jour doivent êtres rapides). Des graphes plus "intelligents" pourront être paramétrables. - le paramétrage des liaisons en fonction du type de noeuds et liaisons - le calcul de l'energie du graphe(et donc sa minimisation) "H-TREE" : Les arbres de type H-TREE sont des arbres binaires. Un enfant est toujours placé horizontalement à droite ou verticalement en bas de son père L'algorithme est récursif et du type Bottom-UP.

"Radial Tree" Les noeuds de même niveau sont positionnés sur le même cercle. Tous les cercles sont concentriques à la racine.
"Balloon" : Chaque couche est dessinée sur un cercle dont l'origine a été positionnée sur la couche inférieure. L'algorithme minimise l'espace requis en 2 passes(Bottom-Up,et Top-Down)
Tree-Maps : Le principe est d'affecter à chaque noeud une valeur numérique représentative de la taille ou de la complexité du sous-arbre enraciné à ce noeud. Chaque noeud (et ses enfants)est affiché sous forme d'un rectangle proportionnel à sa valeur.

Boite de Sugiyama

Arbre conique Les sommets de chaque cone sont les péres et les enfants sont placés à la base du cone.

Disposition hyperbolique Le Layout hyperbolique des graphes est une des plus récentes formes de disposition de graphes .Son interêt tient du fait qu'on dispose de plus d'espace en Hyperbolique qu'en Euclidien(croissance exponentielle) .L'algorithme procéde en 2 phases. .Construction dans un espace hyperbolique de dimension supérieure(en général espace de Minkowski) .Projection dans l'espace euclidien(en général dans le disque/sphére de rayon unité de Klein-Beltrami ou de Poincaré).


NAVIGATION DANS LES GRAPHES


Zoom Le zoom (Loupe) est soit: Géometrique (affichage d'une zone en plus gros) Sémantique (affichage de plus de détails) Fisheye Le "fisheye" consiste à modifier: la position de l'oeil(foyer) et/ou la valeur de distorsion. Distortion de fisheye La distance de chaque noeud par rapport à l'oeil est calculé par une fonction de distorsion qui peut être lineaire ou non lineaire(loi sigmoide par exemple). Exploration incrementale Son principe est d'afficher une petite partie du graphe (fenetre que l'on deplace)

CLUSTERISATION DES GRAPHES


Principe général Pour les graphes de trés grande taille,il est intéressant de réduire la dimension du probléme à un certain nombre de classes,appelées clusters. Les techniques habituelles de classification sont utilisables (exemple;les fonctions noyau ou les nuées dynamiques). Après avoir calculé le nombre de classes, le nombre d'éléments à afficher se limite donc aux classes elles-mêmes. Le layout fournit une vue d'ensemble du graphe et permet de maintenir un contexte tout en réduisant la complexité visuelle. La plupart des algorithmes recherchent un équilibre entre le nombre de clusters et le nombre de noeuds dans ces derniers. Un nombre restreint de clusters permet un traitement et une navigation rapide mais une perte d'information importante . La classification la plus commune consiste à trouver des clusters qui s'excluent mutuellement. Il est possible également de définir une classe avec un nombre minimum de liaisons(pondérées ou pas) entre les noeuds. Layout des clusters On représente en général les clusters avec des "glyphes" et on les traite comme des super-atomes. Le layout est en général hiérarchique,du type CAH.les algorithmes utilisés sont du type MST (Minimum Spanning Tree). Ci-dessous, le layout hierarchique d'un graphe de clusters .

(SOMMAIRE)


Webmaster:
Last revised:11/04/2001