Génération de graphes avec GraphViz

Nous téléchargeons le fichier graphviz-1.9.exe et exécutons le programme d'installation qui installe l'application GraphViz (bin/), la documentation (doc/) et de nombreux exemples (graphs/) de fichiers d'entrée définissant des graphes orientés (directed/) et non orientés (undirected/).

Le répertoire d'installation est le suivant : C:\Programmes Files\ATT\GraphViz\ .

Installation de GraphViz sous Windows XP

L'interface Windows GVUI.exe appelle le programme générateur dot, neato ou twopi selon votre choix. Les différences entre ces générateurs seront expliquées plus loin.

Nous téléchargeons le fichier graphviz-1.9-0.i386.rpm et installons le package comme suit :

rpm -i graphviz-1.9-0.i386.rpm

La génération de graphe nécessite que des polices de caractères TrueType soient présentes sur le système, pour cela il est nécessaire de copier les fichiers de police correspondants dans un répertoire du système et d'en spécifier le chemin à GraphViz. Nous téléchargeons alors l'archive FreeType-compatible dans le thème Fonts de la page de téléchargement.

Vérifiez également que les librairies suivantes : freetype2, libjpeg, libpng, libz sont bien installées sur votre système.

Exemple :

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

Dessin du graphe non orienté

Cet exemple dessine un graphe non orienté. Le fichier d'entrée commence par la déclaration du type de graphe : graph pour graphe non orienté. Puis on nomme notre graphe : G. Et enfin, on écrit la liste des nœuds et liens entre accolades { }. Les liens non orientés sont représentés par deux tirets : --. Il n'est pas nécessaire de déclarer au préalable les nœuds avant de les lier entre eux, sauf à devoir en spécifier les attributs d'affichage (couleur, forme...).

Exemple :

digraph G {
        a;
        b;
        c -> d;
        a -> c;
}

Dessin du graphe orienté

Cet exemple dessine un graphe orienté. La déclaration du type de graphe est différente : digraph. Quant aux liens, ils sont représentés par des flèches : ->.

La syntaxe du fichier d'entrée est assez souple, un même graphe peut être écrit de multiples manières. D'autant que certains procédés syntaxiques permettent de gagner beaucoup de temps et de place en terme de quantité de caractères à écrire.

digraph G {
        a -> b -> c;
        e -> {f; c; a;}
}

Dessin de graphe orienté

Dans cet exemple, on utilise deux nouvelles syntaxes :

1. liens en bus, les nœuds se suivent et chacun est lié à son suivant
2. liens en étoile, un nœud est lié à chacun des autres déclarés entre accolades et séparés par un point virgule

Cette souplesse syntaxique permet d'écrire en une seule ligne du fichier d'entrée :

1. les longues branches
2. les étoiles denses

La syntaxe est la même pour les graphes non orientés :

graph G {
        a -- b -- c ;
        e -- {f; c; a;}
}

Dessin de graphe non orienté

Il suffit de prendre garde à bien définir le bon type de graphe et de liens. Et c'est vraiment très pratique, et surtout plus lisible.

Les identifiants des nœuds sont alphanumériques. Ils peuvent contenir des chiffres, des lettres, des caractères de soulignement. Mais le premier caractère ne doit pas être un chiffre s'il ne constitue pas à lui seul l'identifiant. Les identifiants peuvent contenir des caractères accentués à la condition que l'identifiant soit protégé par des doubles quotes :

digraph G {
        y -> 5 -> aa;
        foo -> bar;
        toto -> "roméo" -> aa;
}

Comme le montrent les exemples précédents, le dessin d'un graphe est par défaut d'aspect plutôt austère. Sachez que le dessin est entièrement paramétrable : les formes et couleurs peuvent être paramétrées à loisir.

V-E-1. V-E-1. Propriétés générales▲

digraph G {
        bgcolor=azure;
        node [shape=box, color=lightblue2, style=filled];
        edge [arrowsize=2, color=gold];
        "zero" -> "dix";
        "un" -> "dix";
        "zero" -> "vingt";
        "deux" -> "vingt";
}

V-E-2. Propriétés particulières▲

digraph G {
        bgcolor=azure;
        node [shape=box, color=lightblue2, style=filled];
        edge [arrowsize=2, color=gold];
        "zero" -> "dix" [color=purple];
        "un" -> "dix";
        "zero" -> "vingt";
        "deux" -> "vingt";
        "zero" [shape=circle, color=thistle1, fontcolor=purple];
}

V-E-3. V-E-3. Principaux attributs▲

digraph G {
        graph [bgcolor=lightyellow2, splines=true];
        edge [color=red, arrowsize=2];
        node [color=yellow, style=filled, shape=polygon, sides=6, fontname="Verdana"];
        A1 -> A3 [label="est parrain de", arrowtail=dot, arrowhead=open];
        A3 -> A5;
        A3 -> A6;
        A2 -> A4;
        A1 [label="Hugo", shape=circle, color=blue, fontcolor=white];
        A2 [label="Boris"];
        A3 [label="Cécile"];
        A4 [label="François"];
        A5 [label="Frank"];
        A6 [label="Elise"];
}

L'interface Windows est d'utilisation intuitive :

1. on choisit le générateur parmi les trois disponibles
2. on sélectionne le fichier de description du graphe
3. on saisit le nom du fichier de sortie à générer
4. ainsi que le type de sortie
5. on peut éventuellement spécifier une liste d'arguments à passer au programme
6. et enfin on génère le graphe (Do Layout) qu'on peut par la suite visualiser (View Output)
7. on pourra remettre à zéro les paramètres de l'interface (Clear) où fermer (Close)

GUI Windows

GraphViz ne possède pas d'interface graphique sous Linux, il est utilisé en ligne de commande en passant en paramètre le nom du fichier d'entrée contenant la déclaration du graphe ou bien par l'écriture dans le flux d'entrée de cette déclaration.

Syntaxe (où cmd correspond à l'un des générateurs : dot, neato, twopi) :

cmd [ flags ] [ input files ]

Exemple produisant une image JPEG à partir du fichier d'entrée monGraphe.dot :

dot -Tjpg -omonImage.jpg monGraphe.dot

VI-C-1. Bibliothèque PEAR Image_GraphViz▲

Exemple d'utilisation de la classe Image_GraphViz
// inclusion de la classe Image_GraphViz
require_once 'Image/GraphViz.php';
// création de l'objet graphe
$graph = new Image_GraphViz();
// ajout des noeuds du graphe
$graph->addNode('Node1', array('URL' => 'http://link1',
                               'label' => 'This is a label',
                               'shape' => 'box'
                               )
);
$graph->addNode('Node2', array('URL' => 'http://link2',
                               'fontsize' => '14'
                               )
);
$graph->addNode('Node3', array('URL' => 'http://link3',
                               'fontsize' => '20'
                               )
);
// ajout des arcs entre les noeuds et spécification de quelques attributs
$graph->addEdge(array('Node1' => 'Node2'), array('label' => 'Edge Label'));
$graph->addEdge(array('Node1' => 'Node3'), array('color' => 'red'));
// création de l'image de sortie représentant le graphe
$graph->image();

VI-C-2. Script PHP personnalisé▲

<?php
$type = "jpg";
$file = "monGraphe";
if($fp = fopen($file.'.dot', "w")) {
        fputs("digraph G {");
        fputs("\t edge [color=red, arrowsize=2];");
        fputs("\t node [color=lightyellow2, style=filled];");
        if($result = mysql_query("SELECT * FROM parainnage")) {
                while($ligne = mysql_fetch_array($result)) {
                        fputs("P" . $ligne['parrain_id'] . " -> F" . $ligne['filleul_id'] . ";");
                        fputs("P" . $ligne['parrain_id'] . " [label=\"" . $ligne['parrain_nom'] . "\"];");
                        fputs("F" . $ligne['filleul_id'] . " [label=\"" . $ligne['filleul_nom'] . "\"];");
                }
        }
        fputs("}");     
        fclose($fp);
        exec("dot -T$type $file.dot");
        echo "<img src=\"$file.$type\" alt=\"graphe des parrainages\" />";
}
?>

digraph G {
        edge [color=red, arrowsize=2];
        node [color=lightyellow2, style=filled];
        A1 -> A3;
        A3 -> A5;
        A3 -> A6;
        A2 -> A4;
        A1 [label="Hugo"];
        A2 [label="Boris"];
        A3 [label="Cécile"];
        A4 [label="François"];
        A5 [label="Frank"];
        A6 [label="Elise"];
}

De la même manière, avec tout autre langage (Java, Perl, ASP.NET, etc.) nous pouvons réaliser un fichier d'entrée, le soumettre au générateur de GraphViz puis en exploiter le fichier de sortie pour l'afficher directement ou l'analyser pour en générer une représentation dans un autre format (Flash ou autre...).

Le programme dot dessine les graphes orientés comme des hiérarchies en les représentant par niveaux en fonction du nombre de prédécesseurs de chacun des nœuds.

Il procède en quatre étapes :

1. suppression des cycles
2. assignation d'un rang à chacun des nœuds en fonction de la longueur du plus court chemin le séparant du nœud de départ, en vue de déterminer leur position sur l'axe des Y
3. ordonnancement des nœuds en fonction de leur rang
4. détermination de leur position sur l'axe des X afin de minimiser la longueur des arcs dans le dessin

Les dessins ont ainsi l'aspect particulier des arbres. Il en découle pour les graphes denses des arcs particulièrement "tordus" calculés par des splines aux angles parfois aigus. Il est adapté à la représentation d'organigrammes, des dépendances dans un programme...

Image générée avec Dot

Le programme neato trace des graphes non orientés. Il se base sur le modèle de dot mais utilise des heuristiques particulières afin de tracer des graphes dont la configuration est de moindre énergie. On retrouvera donc des tracés en forme de cercle avec un centre de gravité central et une répartition homogène des nœuds tout autour de ce centre. Il s'attache à ce que les distances des arcs dans le dessin soient le plus proche de celles dans la représentation théorique. Ainsi, un arbre très dense sera représenté comme une fractale dont le centre est le sommet de l'arbre et les branches se déploient tout autour.
Il est particulièrement adapté à la représentation de systèmes de télécommunication réseau, à l'ingénierie logicielle...

Image générée avec Neato

Le programme twopi trace des graphes en affichant les étoiles sous forme de cercle contrairement à dot. De plus il gère autant les non orientés que les orientés contrairement à neato.