Génération de graphes avec GraphViz

Date de publication : 23/01/2004 , Date de mise a jour : 28/01/2004

Par Hugo Etiévant (Le CyberZoïde Qui Frétille)
 

Cet article présente la génération de graphes orientés à l'aide de l'outil open-source GraphViz.

I. Avant Propos

II. Présentation de GraphViz

L'application  GraphViz permet de représenter graphiquement des graphes. Elle a été conçue par une équipe des laboratoires de recherche de  AT&T (American Telephone & Telegraph).

Aperçu de graphes produits par GraphViz

III. Installation

Vous pouvez télécharger les sources ou les binaires (setup Windows, rpm Redhat ou Debian) de GraphViz sur le site  http://www.graphviz.org.

III-A. Installation sous Windows XP

Installation de GraphViz sous Windows XP

III-B. Installation sous Linux ReadHat 9

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.

IV. Formats de sortie

Format	Description
fig	Image vectorielle de l'utilitaire XFig pour Linux
gd	Image de la librairie GD pour PHP
gif	Graphics Interchange Format, format le plus populaire sur le Net
cmap	Description des zones réactives HTML
jpg	Image compressée standard du Net
plain	Description texte du graphe avec les coordonnées des nœuds et arcs
png	Image compressée standard du Net
ps2	PostScript pour PDF (Portable Document Format)
svg	Format vectoriel  SVG d'Abobe

• Malheureusement, du fait du brevet sur le format GIF déposé par les sociétés CompuServe Inc. et Unisys Corporation, il n'est plus possible aux développeurs d'utiliser ce format sauf à payer des royalties.
• Le PDF qui est le format de référence pour la communication de documents à travers le Net, n'est pas généré directement pas GraphViz mais doit résulter du traitement du format PS2 par un programme de conversion. Pour cela il existe un utilitaire Unix : ps2pdf qui s'utilise en ligne de commande suivant la syntaxe : ps2pdf source.ps destination.pdf.
• Le format texte PLAIN pourra aisément être utilisé pour générer en Flash via PHP des graphes dynamiques d'un design très évolué. Il peut aussi être utilisé avec les librairies  EzPDF (1) ou  FPDF via PHP pour générer du PDF.
• Le format GD de la librairie  GD communément utilisée en C et en PHP pour la manipulation d'images permet de personnaliser le graphe par l'ajout de titres, légendes, mentions légales, etc. en PHP.
• Le format CMAP associé au GIF, PNG ou JPG permet de créer des zones réactives en HTML afin de rendre le graphe dynamique par l'ajout de liens hypertextes.

V. Fichier d'entrée

V-A. Graphe non orienté

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

Dessin du graphe non orienté

V-B. Graphe orienté

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

Dessin du graphe orienté

V-C. Souplesse syntaxique

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

Dessin de graphe orienté

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

1. les longues branches
2. les étoiles denses

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

Dessin de graphe non orienté

V-D. Identifiants

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

V-E. Attributs

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";
}

Illustration des propriétés générales

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];
}

Illustration des propriétés particulières

V-E-3. Principaux attributs

• au graphe dans son entier
• aux noeuds sélectionnés
• aux liens (orientés ou non) sélectionnés

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"];
}

Dessin du graphe avec quelques attributs de mise en forme

Pour la liste hexaustive des attributs et valeurs d'attributs possibles, reportez-vous à la documentation en ligne de GraphViz sur le site officiel.

VI. Interface de commande

VI-A. GUI Windows

1. on choisit le générateur parmis les 3 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

VI-B. En ligne de commande

cmd [ flags ] [ input files ]

dot -Tjpg -omonImage.jpg monGraphe.dot

VI-C. Scripting PHP

VI-C-1. Bibliothèque PEAR Image_GraphViz

L'interface PHP du  PEAR Project : la classe  Image_GraphViz de Sebastian Bergmann permet de faire le lien entre un script PHP et le programme GraphViz installé sur le serveur web.

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é

Exemple de génération d'un graphe
<?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 parrainage\" />";
}
?>

Exemple de fichier d'entrée généré
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"];
}

Exemple de graphe de parrainage généré

VI-D. Autres langages

VI. Les différents générateurs

graph G {
	a -- b -- c -- d -- e;
	1 -- {2; 3; 4; 5; 6; 7;}
}

Différences de dessin entre générateurs

VI-A. Dot

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

Image générée avec Dot

VI-B. Neato

Image générée avec Neato

VI-C. Twopi

VIII. Conclusion

Nous avons pu constater la souplesse et l'efficacité de l'outil GraphViz. Sa documentation utilisateur est assez dense, et les articles techniques sur les algorithmes employés sont également en nombre sur le site officiel. Cet outil fait l'objet de mises à jour régulières (on est passé de la 1.3 à la 1.9 en 10 mois) et est développé par une équipe d'experts. Il a même été adopté par l'outil de documentation de sources  Doxygen (2) pour générer les graphes de dépendance. En outre il s'interface à merveille avec tout logiciel. Et la diversité des formats de sortie est un gage de souplesse et de portabilité.

Remerciements

(1)	La librairie EzPDF fait l'objet d'un tutorial complet sur Developpez.com :  Création de documents PDF avec la classe EZPDF de R&OS Ltd de Hugo Etiévant
(2)	L'outil Doxygen fait l'objet d'un tutorial sur Developpez.com :  Documenter un projet avec Doxygen 1.3.8 par Hugo Etiévant