User Tools

Site Tools


etcheverry_farau:etcheverry_jeremy_farau_romain

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Jérémy Etcheverry & Romain Farau's corner

Graph Drawing: The SHriMP visualization technique

Présentation globale du sujet


Notre travail consistait à ajouter un plugin, de type “interactor”, sur tulip.
Ce plugin devait appliquer l'algorithme de SHriMP sur un graphe.

De manière générale, cet algorithme permet de mettre en avant une portion d'un graphe qu'on aura sélectionné, en zoomant sur celle-ci et en diminuant le reste du graphe, tout en gardant la forme globale du graphe.
C'est-à-dire, en préservant sa topologie.

Deux variantes sont énoncées dans notre article :

  1. la première, préservant l'orthogonalité d'un graphe,
  2. la seconde, préservant la proximité.

Illustrations :

Légende : La première image représente le graphe initial. Sur la seconde et la dernière, on a les versions représentant respectivement la préservation de l'orthogonalité et de la proximité.

Bien evidemment ces deux alternatives ne sont pas les deux seules solutions existantes, on peut en imaginer d'autres, tel que, par exemple, une version hybride combinant un peu les deux ci-dessus. Dans l'article, les auteurs ont réfléchis au cas où notre graphe aurait une structure arborescente. Ils ont donc pensé à un algorithme étant plus accès sur la préservation de la parallélisation des noeuds.

Travaux effectués


Nous avons commencé par essayer d'ajouter un plugin sur tulip. Nous avons donc testé avec un plugin déjà existant, dont on avait juste changé le nom.
Pour faire cette étape, nous avons rencontré quelques problèmes que l'on présentera dans la partie “Difficultés rencontrées”.
Une fois l'intégration d'un plugin sur tulip réussie, nous avons implémenté les deux algorithmes présentés ci-dessus.
La version sur l'orthogonalité fonctionne mais ne donne pas exactement le même résultat que dans l'article.
Pour ce qui est de la version sur la proximité, on a bien implémenté l'algorithme commme indiqué sur l'article, en utilisant et respectant les formules, mais la représentation ne donne pas des résultats attendus, ni même cohérents.
Nous pensons avoir une erreur quelquepart, ou mal compris une spécificité de tulip, mais ne l'avons pas trouvé, par manque de temps. Le plus probable est que les données envoyées à notre fonction ne sont pas les bonnes, notamment les coordonnées du centre. En effet, nous avons remarqué qu'il y a plusieurs sortes de centres calculés, tels que le centre de la sélection par rapport à la taille de l'écran, et le centre de la sélection par rapport à la taille de la sélection. Plus particulièrement, la partie du code qui remet le centre à l'origine (quelle origine?) nous a semblé très flou.

        Coord center(editLayoutCenter);
        center *= -1.;
        //move the center to the origin in order to be able to scale
        ....
        _layout->translate(center, itN, itE);
        ....
        //replace the center of the graph at its originale position
        center *= -1.;
        ...
        _layout->translate(center, itN, itE);

Enfin, le fichier .so du plugin a bel et bien été généré comme demandé, cependant, lorsqu'on le met dans le dossier “~/.local/share/data/Tulip 4.3/plugins”, afin que notre plugin soit chargé par le tulip installé sur nos sessions à la FAC, cela ne fonctionne pas.
Nous pensons que c'est à cause du Warning suivant, que l'on obtient lorsque l'on lance le tulip installé à la FAC.

   loadPlugins info: /net/cremi/jetcheve/.local/share/data//Tulip 4.3/plugins//lib/tulip/ - Aucun fichier ou dossier de ce type
Visualisations Obtenues


Nous avons utilisé notre plugin sur un jeu de données semblable à celui présenté dans l'article, afin de mieux comparer nos résultats.


On peut voir respectivement ci-dessus, le jeu de donnée initial, puis la partie selectionnée et enfin l'application de l'algorithme (version orthogonalité).
On retrouve bien un résultat préservant l'orthogonalité, avec des noeuds poussés vers les 4 coins.

Difficultés rencontrées


La principale difficulté que nous avons rencontré concerne l'utilisation de tulip de manière générale.
En effet, tulip est un très gros projet et de surcroît complexe. Nous n'avons pas l'habitude de travailler sur d'aussi gros projets, avec autant de fichiers.
Par exemple, pour installer tulip à partir de ses sources, il est nécessaire d'avoir un certain nombre d'outils et de librairies.

  1. libqt4-dev
  2. libfreetype6-dev
  3. zlib1g-dev
  4. libglew-dev
  5. libjpeg-dev
  6. libpng12-dev
  7. build-essential
  8. cmake
  9. doxygen
  10. libxml2-dev
  11. qt4-dev-tools
  12. python2.7-dev

Nous avons donc passé une bonne partie de notre temps à comprendre le fonctionnement de tulip et réussir à ajouter un plugin.
L'un des points forts de tulip, c'est qu'on est censé pouvoir lui ajouter un plugin sans modifier le code source d'origine. Il suffit pour cela de mettre dans un dossier à part le code du plugin et un fichier “CMakeLists.txt”, qui lorsqu'il est bien fait, permet de compiler le plugin et de l'inclure à tulip.
Le problème est que nous n'avons pas réussis cette étape, malgrè les tutoriaux à notre disposition (certains ne sont plus à jours), ainsi que des exemples de CMakeLists.txt.
Nous avons essayé de voir avec un autre groupe qui a un projet semblable, mais le même problême était rencontré.
Nous pensons que c'est à cause de certains tags à remplir, qui sont, soit manquants, soit mal remplis, lors de l'utilisation de cmake-gui pour configurer la compilation.

Face à ce problème, afin de ne pas perdre plus de temps, nous avons décidé de rajouter notre plugin directement dans le code source fourni.
Nous avons donc rajouté le dossier “interactorPluginShrimp” dans “tulip/plugins/intercator/”, l'endroit comprenant les plugins de type “interactor”.
En compilant avec QtCreator, cela a fonctionné, avec un “CMakeLists.txt” quasi-identique à celui cité précédemment.

Une fois l'ajout d'un plugin réussit, il ne nous restait plus qu'à implémenter notre propre code. La seule difficulté restante était de comprendre le fonctionnement de tulip, à savoir, comment faire telle ou telle chose, que fait telle ou telle méthode, à quoi sert telle variable …
La documentation de tulip, accessible sur internet, a été très utile.

Par exemple, nous avons pu déterminer que le code ci-dessous permettait de récupérer tous les noeuds et arêtes qui ont été séléctionnés par le plugin de de sélection.

  Iterator<node> *itN = _selection->getNodesEqualTo(true, _graph);
  Iterator<edge> *itE = _selection->getEdgesEqualTo(true, _graph);
Améliorations possibles


- On pourait permettre à l'utilisateur de choisir, graphiquement, quel type d'algorithme utiliser.
- Trouver et corriger l'erreur pour la méthode de proximité.

Conclusion


Pour conclure, nous avons trouvé le sujet très intéressant et malgrè les difficultés, cela nous a permis de voir la complexité que représentait la reprise d'un projet conséquent dans sa globalité.
Nous avons également pu mieux connaître tulip, et pu voir en pratique l'importance d'un code bien commenté pour un utilisateur extérieur. Nous avons également vu qu'une grosse partie d'un projet peut être de maitriser le fonctionnement interne d'un logiciel, et pas la difficulté relative des algorithmes à implémenter.

Sources


Les sources du plugin sont dans l'archive suivante.
Pour ajouter le plugin à tulip, suivez les instructions données dans le README.txt.

pluginshrimp-jetcheverry-rfarau.zip

Dans les gros fichiers tels que LayoutProperty.cpp ou InteractorPluginShrimp.cpp, nos parties implémentées sont indiquées par un commentaire, donc pour les retrouver, il suffit de faire une recherche du mot “SHRIMP”.

Références


- Articles :
Graph Layout Adjustment Strategies
By Margaret-Anne D. Storey and Hausi A. Miiller
School of Computing Science, Simon Fraser University, Burnaby, BC, Canada.
Department of Computer Science, University of Victoria, Victoria, BC, Canada.\\

- Sites :
http://tulip.labri.fr/Documentation/4_4/tulip-dev/html/installation.html
http://tulip.labri.fr/TulipDrupal/?q=node/1481
http://tulip.labri.fr/TulipDrupal/?q=node/1461
http://tulip.labri.fr/Documentation/4_4/doxygen/index.html

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/etcheverry_farau/etcheverry_jeremy_farau_romain.txt · Last modified: 2014/01/17 11:23 by jetcheverry