Sortie de GraphStream  1.0

Posté par . Modéré par Nÿco. Licence CC by-sa
30
25
mai
2011
Science

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 :

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.

Un rendu de graphe avec couleurs et tailles aléatoires

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 (Systèmes d’Information Géographique).

Exemple de graphe produit à partir du shapefile de la ville du Havre

Le code du projet GraphStream est distribué sous une double licence LGPLv3 / CeCILL-C et est hébergé sur GitHub.

  • # 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⁶

  • # gs-geography

    Posté par . É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 . É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 . Évalué à -3.

    ... Existe aussi en C++?

  • # La concurrence

    Posté par . É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 . É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.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.