Follow me
RSS feed
My sources
My Viadeo

Ruby/GraphViz 1.0.0

Greg | 09 May 2011

Projets Après 32 versions 0.X et un peu plus de 6 ans de développement, la version 1.0.0 de Ruby/GraphViz vient de sortir. Il est donc temps de consacrer un petit article à ces 4500 lignes de code, dont ~1800 pour les tests. D'en profiter pour remercier les 14 personnes qui ont participé à son développement, et de rendre un petit hommage aux utilisateurs qui vont permettre de bientôt passer la barre des 40000 téléchargements.

Un peu d'histoire...

Une première version en C

La toute première version de Ruby/GraphViz, dont les sources sont encore disponibles, était écrite en C. A l'origine, ce module faisait partie du projet Ruby/ASP qui avait pour ambition de créer un portage d'apache-asp en Ruby. Dans les faits, j'ai longtemps utilisé apache-asp pour développer Webtime, outil de timesheet. Et, vous l'aurez compris, j'avais l'espoir de le réécrire en Ruby.

Quel rapport avec GraphViz ?

Et bien j'envisageais d'ajouter à Webtime des fonctionnalités nécessitant la mise en place de graphes. Ceci afin de permettre de présenter des organigrammes, des schémas de dépendances entre projets, etc...

Dans les faits, tout ne s'est pas exactement passé comme prévu. En effet, Ruby On Rails a fait son apparition, l'été 2004, alors que je commençais tout juste à travailler sur Ruby/GraphViz et la version Ruby de Webtime. J'ai essayé d'être assidu jusqu'à début 2005 avant de me rendre à l'évidence, ROR avait bien plus d'intérêt. J'ai donc laissé tomber Ruby/ASP, j'ai mis de côté Ruby/GraphViz et j'ai même abandonné définitivement Webtime.

2007, redémarrage du projet

Pourquoi 2007 ? Très honnêtement, je ne sais plus. Quoi qu'il en soit, depuis, le rythme de développement n'a fait qu'accélérer, notamment grâce au nombre croissant de contributeurs. Et pourtant, même s'il est assez difficile d'intéresser du monde en proposant de faire de la représentation de graphe, il existe bien un besoin qui a permis au projet d'avoir une seconde naissance.

Si les demandes de corrections ou d'améliorations sont beaucoup plus sporadiques que sur des projets plus grand public, elles sont aussi parfois plus spécifiques. L'ajout du support de GraphML ou des options scale, inverty et Lx en sont un bon exemple.

Quoi qu'il en soit, depuis 2007, Ruby/GraphViz a fait de grands progrès et couvre maintenant totalement le périmètre fonctionnel de GraphViz, et cela aussi bien avec Ruby MRI (1.8 et 1.9) que JRuby, MacRuby ou Rubinius.

Il faut également noter que certaines fonctionnalités ont été laissées de côté. C'est par exemple le cas de FamilyTree. Cette extension a pour objectif de permettre de créer facilement des arbres généalogiques.

graphviz

Cet abandon n'est que temporaire et cette fonctionnalité a été mise de côté afin de faire avancer le projet core. Mais j'ai la ferme intention d'y revenir. Je souhaiterais également proposer de nouvelles fonctionnalités telles que la génération de graphes UML (entre autres).

graphviz

J'en reparlerais un peu plus tard, mais Ruby/GraphViz contient également divers outils. Là aussi, j'ai l'intention d'en ajouter de nouveau, le plus demandé concernant la possibilité de créer des graphes de base de données.

Ruby/GraphViz... concrètement.

Des graphes...

L'ambition première de Ruby/GraphViz était de permettre de créer des graphs via la librairie GraphViz. Ceci peut très facilement être fait en écrivant un script dot et en l'envoyant à un des outils de mise en page disponible.

Avec le langage DOT, un graphe est décrit de la façon suivante :

graph G {
  a -- b
  a -- c
}

Nous pouvons ensuite générer le graphe en utilisant le système de mise en page par défait (dot) :

dot -Tpng -omon_graph.png mon_script.dot

Ce qui donnera le résultat suivant :

graphviz

Pour faire la même chose avec Ruby/GraphViz, nous pouvons utiliser ce script :

g = GraphViz::new( :G )

a = g.add_node( "a" )
b = g.add_node( "b" )
c = g.add_node( "b" )

g.add_edge( a, b )
g.add_edge( a, c )

g.output( :png => "mon_graph.png" )

Notez cependant qu'il est aussi possible d'écrire le script suivant, plus court et plus proche de ce que l'on écrit en dot :

GraphViz::new( :G ) { |g|
  g.a - g.b
  g.a - g.c
}.output( :png => "mon_graph.png" )

Ruby/GraphViz supporte l'ensemble des attributs du langage dot. Pour ajouter des attributs à un noeud, nous pouvez passer par le méthode add_node :

c = g.add_node( "c", :shape => "polygon", :sides => 4, :skew => .4, :label => "hello world" )

Ou directement :

g.c :shape => "polygon", :sides => 4, :skew => .4, :label => "hello world"

Le principe est le même pour les arcs. Soit en utilisant la méthode add_edge :

g.add_edge( node_a, node_b, :color => "red", :style => "bold", :label => "100 times" )

Soit directement :

(g.node_a - g.node_b) [:color => "red", :style => "bold", :label => "100 times"]

Il est également possible d'affecter des valeurs par défaut aux noeuds, arcs ou au graphe :

g.node[:shape] = "ellipse"
g.node[:color] = "black"

g.edge[:color] = "black"
g.edge[:weight] = "1"
g.edge[:style] = "filled"
g.edge[:label] = ""

g[:size] = "4,4"

Pour vous en rendre compte des possibilités offertes par les attributs, reportez-vous à la documentation ou aux nombreux exemples fournis.

Le support des clusters est bien entendu présent. Là encore, il existe plusieurs solutions :

g = GraphViz::new( "G" )
# ...
c = g.add_graph( "cluster" )
# ...

ou :

GraphViz::new( "G" ) { |g|
  # ...
  g.cluster { |c|
    // ...
  }
  # ...
}

Dernier petit exemple, avant de vous renvoyer à la documentation, pour vous montrer le support des shapes :

g = GraphViz::new( "structs" )

g.node["shape"] = "record"

g.add_node( "struct1", "shape" => "record", "label" => "<f0> left|<f1> middle|<f2> right" )
g.add_node( "struct2", "shape" => "record", "label" => "<f0> one|<f1> two" )
g.add_node( "struct3", "shape" => "record", "label" => 'hello\nworld |{ b |{c|<here> d|e}| f}| g | h' )

g.add_edge( { "struct1" => :f1}, {"struct2" => :f0} )
g.add_edge( {"struct1" => :f2}, {"struct3" => :here} )

Ce script produira le résultat suivant :

graphviz

...des outils...

Comme je l'ai indiqué un peu plus haut, Ruby/GraphViz contient quelques outils crées au fil de mes besoins. Ces outils sont aujourd'hui au nombre de 5 :

...de la théorie

La partie théorie a fait son entrée il y a peu de temps dans Ruby/GraphViz. Elle se résume pour le moment à quelques algorithmes simples. Cependant c'est une des parties pour laquelle il y a de gros chantiers à venir.

Pour le moment vous pouvez seulement récupérer les matrices d'adjacente, d'incidence et Laplacienne d'un graph, faire une recherche de plus court chemin selon l'algorithme de Dijkstra ou faire un calcul de chemin critique.

Projets annexes

Ruby/GraphViz a été le point de départ de deux projets satellites.

Leonhard

Leonhard est un éditeur de script DOT écrit avec MacRuby. Il s'agit d'un projet très jeune pour lequel j'ai reçu des retours très positifs, et qui devrait donc évoluer très régulièrement.

DotGraph

DotGraph est, quant à lui, un site internet qui à pour objectif d'offrir les mêmes services que WebDot. Ce projet avance de façon privée et est ouvert à une petite dizaine de personnes qui le testent depuis plusieurs mois. Ces tests, qui se fondent sur des besoins de générations de graphes de plusieurs dizaines, ou centaines, de milliers de noeuds, ont permis de challenger très fortement les choix techniques.

Aucune date d'ouverte du service n'est encore planifiée... Le projet avance lentement mais surement ;)

Merci

Pour terminer, je voudrais encore remercier Brandon Coleman, Dave Burt, Miguel Cabrera , obruening, reactive, Hugh Sasse, axgle, hipe, Stefan Huber, Nigel Thorne, Rolf Timmermans, Jonas Elfström et oupo pour leur participation active dans le développement de Ruby/GraphViz.

Il serait également injuste de ne pas remercier Desmond Dsouza qui a effectué les premiers tests et corrections sous Windows, ainsi que Vidar Hokstad et Ryan Shea pour m'avoir autorisé à intégrer nothugly.xsl aux sources de Ruby/GraphViz.

Copyright © 2009 - 2011 Grégoire Lejeune.
All documents licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License, except ones with specified licence.
Powered by Jekyll.