GraphStream, la bibliothèque logicielle en Java de manipulation de graphes dynamiques, est disponible en version 1.0, après plusieurs années de développement.
GraphStream est née de la fusion de diverses parties logicielles développées au fil des ans par les membres de l’équipe RI2C (Réseaux d’Interactions et Intelligence Collective) du LITIS, le Laboratoire d’Informatique du Traitement de l’Information et des Systèmes. Ce projet est né du besoin de manipuler, analyser et visualiser la dynamique des réseaux d’interactions. Le but du projet est de fournir une bibliothèque logicielle répondant à ces besoins, sans fournir le logiciel final.
Nouvelle architecture
Quelques versions mineures de GraphStream ont permis de mieux évaluer les besoins liés à la dynamique, et d’aboutir à une nouvelle architecture, avec la version 1.0, basée sur des sources et des puits. Les sources sont des objets émetteurs d’événements liés à des modifications dans la structure d’un graphe ou dans l’évolution des attributs du graphes, ainsi que des éléments qui le composent (nœuds ou arcs). Les puits, quant à eux, sont des objets capables de manipuler les événements produits par une source. On trouvera aussi des tunnels, qui sont des objets étant à la fois une source et un puits, comme par exemple un serveur mandataire (proxy) entre deux « threads », ou encore un serveur mandataire RMI permettant de diffuser des événements entre plusieurs machines.
Le projet est divisé en plusieurs modules dont les principaux sont :
-
gs-core, contenant la base de GraphStream et permettant de modéliser, lire, écrire et afficher un graphe ; -
gs-algo, composé de différents algorithmes, ainsi que des générateurs de graphes ; -
gs-ui, qui permet un affichage avancé de graphes, en offrant un nouvel afficheur écrit en Scala ; -
gs-tool, un ensemble d’outils.
Lecture / écriture dans des fichiers
Les lecteurs de fichiers sont considérés comme des sources d’événements. Les principaux formats supportés sont :
-
DGS, Dynamic Graph Stream, le format de GraphStream ; -
DOT, le format de GraphViz ; -
GML, Graph Modelling Language.
Les objets permettant l’écriture dans des fichiers sont des puits. Les principaux formats supportés sont :
-
DGS; -
DOT; -
GML; -
PGF/TikZ, un format intégrable dans des documents LaTeX ; -
SVG, [[Scalable Vector Graphics]], format XML bien connu ; -
Images, qui permet de produire une séquence d’images du graphe, afin de créer une vidéo.
Générateurs et algorithmes
Le module « gs-algo » propose un certain nombre de générateurs et d’algorithmes. Les générateurs permettent de produire un graphe de manière algorithmique. On trouvera par exemple le générateur par attachement préférentiel de Barabasi-Albert, les graphes à distribution de degrés en loi de puissance de Dorogovtsev-Mendès, ou encore des grilles…
GraphStream propose un nombre grandissant d’algorithmes classiques ou plus récents sur les graphes, dont certains sont adaptés à la dynamique. On trouve en particulier des algorithmes de plus court chemin, tels que A*, Dijkstra ou APSP, des algorithmes d’arbre couvrant (Kruskal, Prim), des mesures (centroïde, excentricité, centralité d’intermédiarité), etc..
Affichage des graphes
Le cœur de GraphStream permet un affichage simple d’un graphe, la zone de rendu pouvant être utilisée dans une interface de plus haut niveau par la suite. Le module gs-ui fournit un rendu plus performant, avec une interface écrite en Scala.
La personnalisation de l’affichage du graphe est réalisée au travers d’une feuille de style respectant la syntaxe CSS, qui permet de définir le style des éléments graph, node, edge et sprite, ainsi que la couleur, la forme, la taille, etc..
Un module expérimental, gs-geography, permet de produire un graphe à partir d’un fichier de formes ([[shapefile]]) utilisé dans les [SIG].
Le code du projet GraphStream est distribué sous une double licence LGPLv3 / CeCILL-C et est hébergé sur GitHub.
Aller plus loin
- Site de GraphStream (935 clics)
- Vidéo de présentation de GraphStream 1.0 (471 clics)
- GraphStream sur GitHub (160 clics)
- Équipe RI2C du LITIS (99 clics)
- Théorie des graphe sur Wikipédia (137 clics)
# Couper la dépêche en deux ?
Posté par ᴼ ᴹᴬᴺᴺ . Évalué à 1.
Est ce qu'on peut couper la dépêche en deux avec une partie introduction et une partie avec le texte ?
Actuellement la page des dépêches est chamboulée par celle ci qui prend presque tout l’ascenseur de mon navigateur en hauteur.
207829⁶+118453⁶=193896⁶+38790⁶+14308⁶+99043⁶+175539⁶
[^] # Re: Couper la dépêche en deux ?
Posté par Guilhelm Savin . Évalué à 2.
Ce serait peut être une bonne chose en effet ...
Mais il faudrait qu'un modérateur s'en charge je pense, je ne peux pas éditer la dépêche.
[^] # Re: Couper la dépêche en deux ?
Posté par Guilhelm Savin . Évalué à 2.
Merci. Par contre, s'il était possible de remettre l'image de la ville là où elle était (à la fin juste après qu'il soit mention de gs-geography), ce serait super sympa.
Désolé de ce commentaire peu utile.
[^] # Re: Couper la dépêche en deux ?
Posté par ᴼ ᴹᴬᴺᴺ . Évalué à 2.
Merci aux modos !
207829⁶+118453⁶=193896⁶+38790⁶+14308⁶+99043⁶+175539⁶
# gs-geography
Posté par Christophe Turbout . Évalué à 4.
il y a moyen d'avoir un peu d'explication sur le fonctionnement du module car
pas de doc et le source n'est pas nécessairement parlant ...
même si c'est mis "work in progress", peut-on avoir une idée sur les fonctionnalités finales du module ?
[^] # Re: gs-geography
Posté par Ant01n3 . Évalué à 4.
Oui, ça manque un peu de documentation ! Grosso-modo le module pour le moment ne fournit qu'un système de conversion entre les fichiers de données GIS "shape-file" de ESRI, pour les transformer en graphe, en particulier le réseau routier qui s'y prête bien.
Mais a terme, l'idée de gs-geography est d'inclure des algos dédiés, et des conversions à partir d'autres formats (notamment OpenMap) et des outils pour la simulation sur les réseaux routiers. D'ailleurs, tout aide ou connaissance sur le sujet est la bienvenue ;-)
Pour le moment, ce qui est disponible : dans les bases de données géographiques, souvent on a un ensemble séparé de (poly-)lignes qui décrivent des morceaux de routes avec des indications sur chaque morceau pour retrouver à quels autres morceaux ils sont connectés. Ajouté à des lignes qui se croisent mais à différentes hauteurs (ponts, tunnels), etc. C'est en général assez ennuyeux à gérer comme format. Le module propose donc une conversion en graphe, en gérant les ponts, les tunnels, et en copiant les autres données en attributs des éléments du graphe (vitesse max, nombre de voies, type de route, etc.). Il est pour l'instant surtout bien adapté aux bases de données de NavTeq, faute d'autres données pour le tester. Il sert par exemple à faire des simulations routières.
Si vous voulez plus d'infos, n'hésitez pas à envoyer un mail sur la mailing list users@graphstream-project.org
# Intéressant...
Posté par FantastIX . Évalué à -3.
... Existe aussi en C++?
# La concurrence
Posté par Jolow . Évalué à 1.
Super impressionnant !
Mais comment est ce que le projet se positionne vis a vis de par exemple JGraphT et JGraphX ?
[^] # Re: La concurrence
Posté par Guilhelm Savin . Évalué à 3.
Merci.
JGraphT semble principalement axé sur la modélisation de structures et d'algorithmes statiques, même s'il est possible d'écouter les modifications apportées aux structures via un système de listeners. JGraphX quant à lui semble être principalement orienté vers la visualisation de données.
Avec GraphStream, le maître mot est dynamique, c'est à dire que l'architecture toute entière est étudiée pour gérer au mieux la dynamique des graphes. C'est sur ce thème qu'est axé GraphStream et c'est ce qui, je pense, le distingue d'autres librairies de graphes. Pour des raisons pratiques (et puis parce que c'est sympa !), la librairie inclut un outil de visualisation mais cet outil par défaut est quelque chose de simple, l'affichage plus avancé étant un projet à part (
gs-ui).GraphStream n'a cependant pas la prétention de concurrencer d'autres bibliothèques de graphes mais de les compléter sur l'aspect dynamique.
[^] # Re: La concurrence
Posté par Jolow . Évalué à 0.
Merci c'est très clair.
Bon courage avec le projet!
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.