User Tools

Site Tools


delestre_perier:clement_delestre_cynthia_perier

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Clément Delestre & Cynthia Perier's corner

Project Quilts

Le code source du projet ainsi que deux exemples de projets réalisés sous Tulip sont disponibles sur le liens suivant : quilts_cynthia_perier_clement_delestre_bioinformatique.tar.gz

Introduction

Traditionnellement, les graphes sont représentés par des nœuds et des arêtes (éventuellement fléchées). Lorsque la taille des graphes augmente, un problème de visualisation se pose avec l‘augmentation des croisements d’arêtes. Les graphes deviennent alors visuellement obscurs et indéchiffrables.

L’article Visualizing very large layered graphs with quilts de Watson B. et. al présente les Quilts ; une méthode de représentation visuellement attractive des grands graphes en niveaux basée sur les matrices d’adjacence.

Nous avons implémentés et visualisé ces Quilts, ainsi que deux améliorations proposées par l’article : la fermeture transitive à partir d’un nœud et la condensation de la visualisation (“summarization”). Nous présenterons tout d'abord cette méthode, puis la façon dont nous l'avons implémentée dans Tulip et enfin, nous discuterons des avantages et inconvénients de celle-ci ainsi que des améliorations possibles de notre code.

Analyse et Conception

Les graphes en niveaux

Les graphes en niveaux ont un large domaine d'application. Ils peuvent par exemple être utilisés pour représenter une suite d'étapes parmi un processus, une généalogie, ou encore un organigramme au sein d'une entreprise. Généralement, représenter un graphe en niveaux consiste à aligner les nœuds d'un même niveau sur une même ligne. Dans l'article, les arêtes reliant les nœuds d'une couche adjacente sont appelées proper link et les autres skip link.

Problématique : la visualisation

Minimiser les croisements entre arêtes peut faciliter la compréhension visuelle d'un graphe. Néanmoins dans tout graphe, plus le nombre d'arête augmente, plus la visualisation devient confuse. En outre, faire en sorte que les arêtes ne se croisent pas est un problème np complet.

On cherche donc à obtenir une visualisation claire et compréhensible d'un très grand graphe en niveaux, en s'affranchissant du problème des croisements d'arêtes.

Quilts : le principe

Généralités

Quilts permet de représenter de manière simple un graphe en niveaux possédant un nombre important d'arêtes. Cette visualisation est interactive. Elle consiste à améliorer la représentation de la matrice d'adjacence, cette dernière étant utilisée sur des graphes en niveaux ou non (voir figure ci-dessous).

Exemple d'une matrice d'adjacence

La visualisation Quilts, représente chaque nœud par un carré. Ces derniers ont une couleur qui dépend de la couche. Afin de pouvoir les distinguer, chacun des nœuds a une saturation qui lui est propre. Ainsi, chaque niveaux est représentée par un dégradé d'une même couleur. L'alignement des nœuds d'un même niveau dépend de la parité de celle-ci. En effet, les noeuds appartenant aux niveaux paires sont alignés verticalement et ceux appartenant aux niveaux impaires horizontalement.

Quant aux arêtes, elles sont représentées par des points. Tout comme une matrice d'adjacence, elles sont placées à l'intersection entre les deux nœuds qu'elles relient si on est dans le cas d'un proper link. Ces derniers ont tous la même couleur qui leur est propre afin de ne pas les confondre avec les nœuds (dans le cas de l'article tout comme notre projet il s'agit du gris). Quant aux skip links, leur couleur est la même que celle du nœud ciblé. De plus, ils sont placés à la fin d'une ligne ou d'une colonne (suivant la parité du numéro du niveau), comme le montre la figure ci-dessous, issue de l'article. Exemple d'une visualisation de Quilts issue de l'article Visualizing very large layered graphs with quilts de Watson B. et. al

Interactivité

Toujours dans le but de rendre la visualisation la plus limpide possible, la visualisation de Quilts est interactive. En effet, un clic sur un nœud met ce dernier en évidence ainsi que le chemin grâce auquel il est relié aux autres nœuds.

Condensation

Quand les graphes ont un nombre important de nœuds, il peut être nécessaire d'effectuer une condensation (ou summarization). Pour cela, les nœuds sont regroupés et les carrés représentent maintenant des clusters de nœuds. Les skip links et proper links ont une intensité de gris proportionnelle au nombre d'arêtes reliant les deux clusters.

Conception

Tout d'abord, un algorithme générant des graphes en niveaux doit être implémenté. Ce dernier devra générer les deux types d'arêtes (proper links et skip links) de manière aléatoire. Cependant, le nombre de nœuds contenu dans le graphe sera fixé. Afin de réaliser la méthode Quilts, il faudra avoir accès à tout moment au numéro de leur niveau pour un nœud donné. Il faut également mettre une même couleur à chaque niveaux et faire varier uniquement la saturation en fonction du nombre de nœud par niveau. Ces couleurs doivent être bien différenciées. Il faut donc stocker un certain nombre de couleur distinctes. Un script permettant d'afficher la fermeture transitive en fonction d'un nœud sélectionné devra être implémenté. De plus, un script implémentant la summarization devra également être réalisé.

Réalisation et résultats

Génération aléatoire de graphe en niveaux

Avant d'appliquer la représentation de Quilts, il a fallu obtenir des données pouvant être dessinées grâce à un graphe en niveaux. Pour cela, un générateur de graphe en niveaux a été implémenté. Celui-ci fonctionne avec 3 arguments : le nombre de nœuds, le nombre de nœuds par niveau et le nom du fichier de sortie. Les arêtes sont placées aléatoirement dans le graphe. Cependant, leur nombre est fixé et dépend du nombre de nœuds :

  • Le nombre de proper links est de nombre de nœuds du niveau suivant +1. Ainsi on est sûr qu'au moins un nœud par couche possède au minimum 2 proper links
  • Le nombre de skip links est le nombre de niveaux -1.

Les coordonnées des nœuds générés sont calculées automatiquement de sorte que les nœuds d'un même niveau soit alignés horizontalement. En sortie du programme, un fichier au format .tlp est généré pour être visualisé via Tulip (cf figure ci-dessous).

Exemple d'un graphe en niveaux obtenu avec le générateur aléatoire.

Afin d'avoir accès au numéro du niveau pour un nœud donné, le script ajoute une nouvelle propriété pour chaque nœud du graphe.

Il faut noter que si les autres programmes ont été réalisés sous la forme de script python, celui-ci a été implémenté en C++ pour pouvoir obtenir un programme qui génère des graphes en niveaux sans passer par la GUI de Tulip. Il est donc possible d'automatiser la création des graphes.

Représentation des noeuds et des arêtes

Un premier script en python a été réalisé afin de représenter les quilts. Il s’applique sur un des graphes générés précédemment (quelle que soit sa taille, le nombre de nœud par niveau et avec ou sans skip links).

L’algorithme se décompose en plusieurs étapes : le dessin des nœuds (forme, position, couleur), celui des points représentant les arêtes de type proper link (idem) et celui des skip links.

Pour dessiner les noeuds, il faut en premier lieu stocker dans une liste le nombre de points par niveau. Ce nombre permet de déterminer de quelle intensité varie la saturation des nœuds d’un même niveau après transformation.

On parcourt le graphe, et pour chaque niveau on assigne une couleur. On positionne les nœuds un par un côte à côte ou l’un en dessous de l’autre en fonction de la parité de la couche. Les coordonnées en x et y s’incrémentent au fur et à mesure du parcours, et la saturation de la couleur du nœud est elle aussi modifiée. Les nœuds prennent une forme carrée (avec bordure visible).

Dans un second temps l’ensemble des arêtes du graphe est parcouru. Au préalable, elles ont été rendues transparentes (modification du viewColor de telle sorte que alpha=0) pour disparaître de l’écran.

Un sous-graphe est ajouté au graphe racine. Il contient pour chaque arête un nœud dont les coordonnées dépendent de celle de son nœud source et de son nœud cible. Ces nœuds sont gris et 40% plus petits qu’un nœud basique.

Si le numéro du niveau du nœud cible et celui du nœud source diffèrent de plus de 1 (couches non adjacentes), on doit représenter un skip link. Il est positionné tout en bout de ligne ou de colonne. On récupère pour cela la taille de la couche suivante dans le tableau calculé en début de script. S’il y a plusieurs skip links pour un même nœud, il faut en connaître le nombre pour déterminer la position de chacun. On a donc précédemment ajouté une propriété au graphe dans ce but (“numberOfSkipLinks”). Cette fois-ci, la couleur du point est celle du nœud ciblé.

Exemple d'une représentation avec quilts sur un graphe d'une centaine de nœuds

Visualisation du graphe condensé

Un second script a été ajouté afin d’implémenter la fonctionnalité de summarization décrite dans l’article. L’algorithme de base est le même que celui des quilts simples (dessin des nœuds en fonction de la taille des couches, puis des arêtes sous forme de points). Seulement cette fois, un ensemble de nœud est implémenté par un méta-nœud, et leurs liaisons par des méta-arêtes.

La création des méta-nœuds nécessite l’ajout d’une liste de sous-listes de nœuds, chaque sous-liste représentant un niveau. Ainsi il devient possible de simuler les clusters en divisant les niveaux un nombre de fois prédéfini. Si cette variable n’est pas un diviseur de la couche, les nœuds en excès (le modulo) sont rassemblés dans un dernier méta-nœud.

Les méta-arêtes sont également traitées comme dans le premier script, à ceci près que l’intensité de la couleur des points les représentant est proportionnelle au nombre d’arêtes entre les nœuds de deux méta-nœuds. On a donc compté le nombre d’arêtes de niveau inférieur en récupérant les données de chaque méta-arête. Plus ce nombre est grand, plus on décrémente le niveau de gris initial (proche de 255) pour se rapprocher du noir.

Comme les skip links possèdent déjà une couleur ne pouvant varier, c’est l’intensité de gris de leur contour (épaissi pour l’occasion) qui sera modulée de la même façon.

Exemple d'un graphe à 800 nœuds condensé à 4 nœuds par méta-nœud et 16 nœuds par méta-nœud.

Visualisation des liens entre les nœuds

Comme cela a été fait dans l'article, un script permettant d'afficher les différents chemins possibles (c'est-à-dire les nœuds et les arêtes) liés à un nœud en particulier a été implémenté.

Pour le faire fonctionner, ce dernier exige qu'un nœud ait été sélectionné au préalable via l'interface graphique de Tulip.
Ce programme fonctionne de la manière suivante : deux parcours récursifs du graphe sont effectués ; l'un en “montant” (c'est-à-dire en visitant des nœuds qui ont un numéro de couche inférieur) et l'un en “descendant”. Pour chaque nœud visité, l'algorithme teste si des arêtes (en cercle) ayant la même abscisse ou ordonnée (selon la parité de la couche à laquelle il appartient) sont présentes dans le graphe ou non. Si c'est le cas, la couleur de celle-ci est ensuite testée pour savoir s'il s'agit d'un proper link ou d'un skip link :

  • Dans le cas d'un skip link : Si le parcours est descendant alors on continue le parcours du graphe avec le nœud cible de cette arête. Sinon on arête le parcours.
  • Dans le cas d'un proper link : On continue le parcours du graphe avec la cible de l'arête.

Dans les deux cas, une arête est bien sûr ajoutée entre le nœud et l'arête. De plus, les contours de ces derniers sont colorés afin de les mettre en évidence, comme on peut le voir sur la figure ci-dessous.


Exemples d'une sélection d'un nœud sur une visualisation de Quilts


Le même programme fonctionne aussi bien avec un Quilts “régulier” qu'avec un Quilts condensé, comme le montre la figure ci-dessous.

Exemple d'une sélection d'un nœud sur une visualisation de Quilts condensée.

Discussion

Les avantages et les inconvénients

Adaptabilité à la taille :

Quelle que soit la taille du graphe, les nœuds et leurs liaisons sont beaucoup plus visibles que pour une représentation traditionnelle du même graphe. Toutefois, il devient difficile de tirer du sens de ce qu’on voit sans un zoom plus ou moins puissant. Les couleurs sont également moins différentiables. La condensation du graphe permet de pallier à ce problème, au prix d’une légère perte en précision.

Visibilité des arêtes :

Les quilts permettent d’éviter tout croisement d’arête en étalant le graphe. On peut ainsi beaucoup plus facilement suivre les liens entre les nœuds, avec la couleur par exemple ou lorsqu'on utilise le script de sélection. Ce dernier est moins utile quand on l'applique sur un graphe condensé, car une très grande partie des nœuds se retrouve reliée (voir dernière figure de la partie précédente).

Les skip links :

Si les skip links sont une bonne alternative à la représentation des arêtes transversales, elles peuvent gâcher la visualisation lorsqu’elles deviennent trop nombreuses. Dans ce cas là, c’est la représentation en niveaux du graphe elle-même qui devient moins pertinente.

Les améliorations possibles

Il serait possible de réaliser un interactor (en C++) plutôt qu'un script pour l'affichage de la fermeture transitive à partir d'un nœud. Ceci aurait rendu l'interaction avec l'utilisateur plus conviviale. Toujours concernant la sélection d'un nœud, des fonctionnalités peuvent être ajoutées afin d'améliorer le suivi d'un chemin. Par exemple, permettre de cliquer une première fois pour afficher le nœud sélectionné et les arêtes adjacentes à celui-ci, et une deuxième fois pour afficher le reste du chemin. De plus, en captant directement les événements de la souris et du clavier, des combinaisons plus élaborées auraient pu être implémentées : comme par exemple la possibilité de supprimer des arêtes symbolisant la fermeture transitive en cliquant dessus tout en maintenant un bouton enfoncé. Ceci aurait permis de rendre la visualisation plus claire.

Conclusion

Durant ce projet, 4 programmes ont été réalisés :

  1. Un générateur de graphe en niveaux
  2. Un programme permettant d'obtenir une visualisation de Quilts
  3. Un programme permettant d'obtenir un Quilts condensé
  4. Un script permettant d'afficher la fermeture transitive à partir d'un nœud sélectionné

Même si il aurait été souhaitable d'améliorer le programme affichant la fermeture transitive d'un nœud sélectionné afin d'obtenir une interaction plus fluide avec l'utilisateur, l'essentiel de la visualisation de Quilts a été réalisé durant ce projet. Certains défauts dus aux couleurs plus ou moins différentiables et à un grand nombre d'arêtes persistent, mais Quilts permet de visualiser de façon claire un graphe en niveaux. Il serait pertinent d'appliquer cette visualisation, et en particulier le graphe condensé, sur des résultats issus d'un regroupement (« clustering ») de nœuds.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/delestre_perier/clement_delestre_cynthia_perier.txt · Last modified: 2014/01/17 17:08 by cclementddel