Dessin de graphe assisté par un algorithme génétique

Maurin Nadal 1, 2, * Guy Melançon 1, 2
* Auteur correspondant
1 GRAVITE - Graph Visualization and Interactive Exploration
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR
Résumé : Les interfaces de visualisation interactive de graphes représentent aujourd'hui une perspective intéressante pour l'analyse de données, et par extension pour les systèmes d'aide à la décision. Le but de ce projet est d'assister un utilisateur novice dans le cadre du dessin de graphe. Actuellement, une des principales difficultés pour l'utilisateur consiste à choisir l'algorithme de dessin qui conviendra le mieux à son graphe. En effet, il existe un très grand nombre de méthodes possibles et toutes ne sont pas facilement accessibles. La solution envisagée consiste à fournir automatiquement plusieurs dessins viables d'un même graphe. Ces dessins sont générés par un algorithme par modèle de force (système masse-ressort) modifié afin d'être paramétrable sommet par sommet. Les jeux de paramètres sont fournis par un algorithme génétique. Cet article présente principalement une preuve de concept de la possibilité d'utiliser un tel processus pour dessiner tout type de graphe, et plus particulièrement des graphes fortement contraints (angles droits ou parallélismes). Les points abordés sont le modèle masse-ressort utilisé et les modifications qui lui ont été apportées, les caractéristiques principales de l'algorithme génétique mis en œuvre, la métrique de similarité permettant l'évaluation des dessins générés au cours de l'apprentissage et enfin le cas d'application proposé comme preuve de concept.
Type de document :
Communication dans un congrès
Anne Etien. 9ème édition de la conférence MAnifestation des JEunes Chercheurs en Sciences et Technologies de l'Information et de la Communication - MajecSTIC 2012 (2012), Oct 2012, Villeneuve d'Ascq, France. 2012
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00780201
Contributeur : Guy Melançon <>
Soumis le : mercredi 23 janvier 2013 - 14:51:15
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : mercredi 24 avril 2013 - 03:55:44

Fichier

majecstic2012_submission_11.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00780201, version 1

Citation

Maurin Nadal, Guy Melançon. Dessin de graphe assisté par un algorithme génétique. Anne Etien. 9ème édition de la conférence MAnifestation des JEunes Chercheurs en Sciences et Technologies de l'Information et de la Communication - MajecSTIC 2012 (2012), Oct 2012, Villeneuve d'Ascq, France. 2012. 〈hal-00780201〉

Partager

Métriques

Consultations de la notice

525

Téléchargements de fichiers

565