Sortie de GraphStream 1.1

L’équipe de développement de GraphStream a publié le 11 novembre 2011 la version 1.1 de sa bibliothèque de manipulation de graphes dynamiques. Cette nouvelle version corrige un grand nombre de bogues présents dans la 1.0 et détectés avec l’aide d’une communauté d’utilisateurs grandissante. Elle apporte aussi son lot de nouveautés, comme l’ajout de nouveaux formats d’entrée, afin de permettre une meilleure interopérabilité des outils de manipulation de graphes ou encore de nouvelles implantations de graphes plus performantes.

GraphStream est une bibliothèque Java développée sous double licence LGPL/CeCILL-C.

Les principales nouveautés

Les principales nouveautés de cette version sont :

• L’ajout de la gestion des formats GEXF (Gephi), Pajek, GraphML et TLP (Tulip) en entrée, dans le but d’offrir une meilleure interopérabilité avec les autres bibliothèques existantes. Certains analyseurs XML (DOT, GML, Pajek, TLP) ont été [ré]écrits à l’aide d’une grammaire JavaCC, afin de reproduire le plus fidèlement possible les spécifications des différents formats ;

• La possibilité d’accéder aux éléments (nœuds et arcs) grâce à un index de type entier, en plus du traditionnel accès par identifiant, offre de nouvelles perspectives algorithmiques. Cet accès aux éléments plus rapide permet également d’utiliser des tableaux pour implanter des algorithmes de traitement de graphes ;

• Les implantations de Graph (AdjacencyListGraph, SingleGraph et MultiGraph) ont été totalement réécrites. Les résultats en termes de stabilité et de rapidité sont conséquents. Les itérateurs de parcours de graphes, en particulier en largeur et en profondeur, ont été accélérés de manière spectaculaire (voir les comparaisons ci‐dessous) ;

• La notion de « caméra » a été introduite dans la partie visualisation. Dorénavant, chaque vue d’un « viewer » GraphStream retourne un objet « caméra » qui permet une interaction aisée avec la vue (centrer la vue, zoomer, effectuer des conversions d’unités entre le graphe et les pixels, etc.) ;

• L’algorithme de Dijkstra de calcul du plus court chemin a été réécrit en intégrant des structures de données efficaces (les tas de Fibonacci), le rendant significativement plus rapide (voir les comparaisons ci‐dessous).

Comparaison des performances entre 1.0 et 1.1

Le tableau suivant montre les gains de performances des différentes implémentations de Graph entre les versions 1.0 et 1.1 de GraphStream, sur un graph, extrait d’IMDB, d’environ 6 000 sommets et 120 000 arêtes. Chaque ligne représente une mesure. La mémoire est donnée en Mio et les temps en secondes.

	Adjacency List	Adjacency List	Single	Single	Multi	Multi
Mesure	1.0	1.1	1.0	1.1	1.0	1.1
____________	_________	_________	_________	_________	_________	_________
MEMORY	36,88	38,07	55,83	53,04	92,59	64,05
RANDOM_EDGE	19,70	0,01	20,43	0,00	20,93	0,00
TRIANGLE	32,40	2,18	1,43	0,37	2,31	0,60
BFS	30,24	0,68	32,36	0,72	94,16	1,26
DFS	950,26	0,87	926,05	0,87	2942,54	1,51
DIJKSTRA	33,14	3,72	37,63	3,39	213,43	3,54

Les mesures sont les suivantes :

• MEMORY : la taille du graphe dans la mémoire (en Mio) ;
• RANDOM_EDGE : choisir 10 000 arêtes aléatoires ;
• TRIANGLE : compter le nombre de triangles dans le graphe ;
• BFS : parcours en largeur à partir de 100 sommets différents ;
• DFS : parcours en profondeur à partir de 100 sommets différents ;
• DIJKSTRA : 100 exécutions de l’algorithme de Dijkstra avec différents sommets sources.

Ces résultats montrent une amélioration significative des temps d’exécution, parfois de plusieurs ordres de grandeur, sans surcoût au niveau de la mémoire utilisée.

Prévisions pour les futures releases

• Gestion du temps dans les événements : il apparaît que le temps est un facteur important pour l’objet modélisé sous forme de graphe dynamique. Par exemple, dans un graphe représentant des communications (les arcs) entre des personnes (les nœuds), les communications possèdent une date de début et de fin, il est donc important de pouvoir inclure proprement ces informations dans le graphe afin d’en tenir compte dans son analyse. C’est pourquoi la version 1.2 offrira une nouvelle version de DGS, rétro‐compatible, qui permettra d’utiliser les « steps » comme des blocs datés d’évènements. Le format des dates utilisé sera personnalisable dans l’entête du fichier.

• Affichage 3D : ce nouvel affichage permettra, d’une part, l’exploitation de la carte graphique pour le rendu d’un graphe, et d’autre part, d’afficher un graphe dont les coordonnées sont en trois dimensions.

• Un protocole réseau permettra à GraphStream de communiquer avec d’autres applications (quel que soit le langage dans lequel elles sont programmées, leur système d’exploitation ou la machine sur laquelle elles s’exécutent). Cette communication sera bidirectionnelle : elle permettra de générer un graphe dans Graphstream à partir d’évènements originaires d’une application tierce, ou à l’opposé, elle permettra à une application tierce de recevoir les évènements de graphes dynamiques générés par GraphStream.

• Ajout de la gestion en sortie pour différents formats de fichiers : la version 1.1 intègre de nouveaux formats d’entrée, mais ne permet pas pour le moment d’utiliser tous ces formats en sortie. La possibilité d’exporter les graphes dans ces différents formats devrait voir le jour au fur et à mesure des prochaines versions.

• Ajout de nouveaux algorithmes prenant en compte la dynamique des graphes (plus courts chemins, problèmes de flot…), ainsi que l’ajout de mesures de la dynamique des graphes.

Aller plus loin

• Site officiel du projet GraphStream (1645 clics)
• Annonce de la sortie de la 1.1 sur le site (65 clics)
• Vidéo de la version majeure 1.0 (370 clics)