Volume Number: 25 (2009)
Issue Number: 01
Column Tag: Graphics
by Mihalis Tsoukalos
This article presents GraphViz, a very flexible and handy tool that is freely available under an open source license. Graphviz helps you draw, illustrate and present graph structures. Do not be discouraged and please do not think that "drawing graph structures" looks restrictive and limiting - I can promise you that by the end of the article, you will have changed your mind.
The good thing is that Graphviz algorithmically arranges the graph nodes so that the output is both practical and appealing!
The article focuses on using GraphViz from the command line but it also presents the PixelGlow Graphviz version (an application with a GUI) that is exclusively designed for Macs. It also presents Omnigraffle that can also render Graphviz files.
Graphviz can be used in domains such as software engineering, networking, bioinformatics, databases, web structures and knowledge representation. The central part of Graphviz consists of implementations of algorithms for graph layout. Most Graphviz is written in C.
GraphViz (or Graphviz or graphviz) is a collection of tools for manipulating graph structures and generating graph layouts. Graphviz supports either directed or undirected graphs. GraphViz offers both graphical and command-line tools. A Perl to Graphviz interface library is also available, but it is not covered here for reasons of generality. There is also a C++ interface.
Strictly speaking and according to the "The Design and Analysis of Computer Algorithms" book, a graph G=(V, E) consists of a finite and nonempty set of vertices V and a set of edges E. If the edges are ordered pairs of vertices, then the graph is said to be directed. If the edges are unordered pairs, the graph is said to be undirected.
Although it may look strange, the fact is that you can draw remarkable illustrations using Graphviz! Figure 1 demonstrates such a draw - and you did not even have to draw a line!
Graphviz has its own dialect that you will have to learn. The language is simple, elegant and powerful. The good thing about Graphviz is that you can write its code using a simple plain text editor - a side effect of it is that you can easily write scripts that generate Graphviz code. In fact, this article has such a script that is written in Perl - my favorite scripting language.
GraphViz is comprised of the following programs and libraries:
The dot program: a utility program for drawing directed graphs. It accepts input in the dot language. The dot language can define three kinds of objects: graphs, nodes and edges. dot uses a Sugiyama-style hierarchical layout.
The NEATO program: a utility program for drawing undirected graphs. This kind of graph commonly is used for telecommunications and computer programming tasks. NEATO uses an implementation of the Kamada-Kawai algorithm for symmetric layouts.
The twopi program: a utility program for drawing graphs using a circular layout. One node is chosen as the center, and the other nodes are placed around the center in a circular pattern. If a node is connected to the center node, it is placed at distance 1. If a node is connected to a node directly connected to the center node, it is placed at distance 2 and so on.
dotty, tcldot and lefty: three graphical programs. dotty is a customizable interface for the X Window System written in lefty. tcldot is a customizable graphical interface written in Tcl 7. lefty is a graphics editor for technical pictures.
libgraph and libagraph: the drawing libraries. Their presence means an application can use GraphViz as a library rather than as a software tool.
Before I start showing you Graphviz code, I should first describe to you some important information about Graphviz nodes and edges.
Table 1 shows some of the node attributes whereas table 2 shows some of the edge attributes. You can check the Graphviz documentation for the full list of node and edge attributes.
Table 1: Node attributes
Table 2: Edge attributes.
I will now present you with the Graphviz code that generates Figure 1:
Figure 1: A Graphviz example.
/* Courtesy of Ian Darwin <ian@darwinsys.com>
* and Geoff Collyer <geoff@plan9.bell-labs.com>
* Mildly updated by Ian Darwin in 2000.
*/
digraph unix {
size="6,6";
node [color=lightblue2, style=filled];
"5th Edition" -> "6th Edition";
"5th Edition" -> "PWB 1.0";
"6th Edition" -> "LSX";
"6th Edition" -> "1 BSD";
"6th Edition" -> "Mini Unix";
"6th Edition" -> "Wollongong";
"6th Edition" -> "Interdata";
"Interdata" -> "Unix/TS 3.0";
"Interdata" -> "PWB 2.0";
"Interdata" -> "7th Edition";
"7th Edition" -> "8th Edition";
"7th Edition" -> "32V";
"7th Edition" -> "V7M";
"7th Edition" -> "Ultrix-11";
"7th Edition" -> "Xenix";
"7th Edition" -> "UniPlus+";
"V7M" -> "Ultrix-11";
"8th Edition" -> "9th Edition";
"9th Edition" -> "10th Edition";
"1 BSD" -> "2 BSD";
"2 BSD" -> "2.8 BSD";
"2.8 BSD" -> "Ultrix-11";
"2.8 BSD" -> "2.9 BSD";
"32V" -> "3 BSD";
"3 BSD" -> "4 BSD";
"4 BSD" -> "4.1 BSD";
"4.1 BSD" -> "4.2 BSD";
"4.1 BSD" -> "2.8 BSD";
"4.1 BSD" -> "8th Edition";
"4.2 BSD" -> "4.3 BSD";
"4.2 BSD" -> "Ultrix-32";
"4.3 BSD" -> "4.4 BSD";
"4.4 BSD" -> "FreeBSD";
"4.4 BSD" -> "NetBSD";
"4.4 BSD" -> "OpenBSD";
"PWB 1.0" -> "PWB 1.2";
"PWB 1.0" -> "USG 1.0";
"PWB 1.2" -> "PWB 2.0";
"USG 1.0" -> "CB Unix 1";
"USG 1.0" -> "USG 2.0";
"CB Unix 1" -> "CB Unix 2";
"CB Unix 2" -> "CB Unix 3";
"CB Unix 3" -> "Unix/TS++";
"CB Unix 3" -> "PDP-11 Sys V";
"USG 2.0" -> "USG 3.0";
"USG 3.0" -> "Unix/TS 3.0";
"PWB 2.0" -> "Unix/TS 3.0";
"Unix/TS 1.0" -> "Unix/TS 3.0";
"Unix/TS 3.0" -> "TS 4.0";
"Unix/TS++" -> "TS 4.0";
"CB Unix 3" -> "TS 4.0";
"TS 4.0" -> "System V.0";
"System V.0" -> "System V.2";
"System V.2" -> "System V.3";
"System V.3" -> "System V.4";
}
I found this example in the /opt/local/share/graphviz/graphs/directed directory (I use the Macports version of Graphviz). The file is called unix2.dot and (as I told you before) is a plain text file, which means that you only need a simple plain text editor in order to write Graphviz files.
The node [color=lightblue2, style=filled]; line of code declares some global properties about each node of the graph. You can later overwrite the global properties for any given node if you want. The digraph command says that the graph is a directed one. The -> notation is for declaring a directed connection between nodes. Each line of code ends with a semicolon.
In order to create the output file using the command line Graphviz version you will have to type the following in the Mac OS X command line (using the Terminal application):
$ dot -o/Users/mtsouk/unix2.pdf -Tpdf unix2.dot
The -T parameter defines the output format. The list of available output formats is as follows: canon cmap cmapx cmapx_np dia dot eps fig gd gd2 gif hpgl imap imap_np ismap jpe jpeg jpg mif mp pcl pdf pic plain plain-ext png ps ps2 svg svgz tk vml vmlz vrml vtx wbmp xdot xlib.
The -o parameter defines the output file name. Note that both the -T and the -o switches are next to their respective parameter values without a space character between them.
This article section will present some more advanced Graphviz examples.
Please take a look at figure 2. This is a binary tree representation using Graphviz and the dot language. As you will see it is very easy to create it - I think that it would be a lot harder to illustrate it in either Adobe Illustrator or Adobe Photoshop. Better yet, it is also easier to make small or big changes to it.
The Graphviz code for figure 2 is the following:
digraph G
{
graph [bgcolor=gray];
node [style=bold, label="\N", shape=record];
edge [color=blue];
graph [bb="0,0,393,252"];
node0 [label="<f0> | <f1> J | <f2> ", width="0.83", height="0.50"];
node1 [label="<f0> | <f1> E | <f2> ", width="0.89", height="0.50"];
node4 [label="<f0> | <f1> C | <f2> ", width="0.89", height="0.50"];
node6 [label="<f0> | <f1> I | <f2> ", width="0.83", height="0.50"];
node2 [label="<f0> | <f1> U | <f2> ", width="0.92", height="0.50"];
node5 [label="<f0> | <f1> N | <f2> ", width="0.92", height="0.50"];
node9 [label="<f0> | <f1> Y | <f2> ", width="0.92", height="0.50"];
node8 [label="<f0> | <f1> W | <f2> ", width="0.94", height="0.50"];
node10 [label="<f0> | <f1> Z | <f2> " width="0.89", height="0.50"];
node7 [label="<f0> | <f1> A | <f2> ", height="0.50"];
node3 [label="<f0> | <f1> G | <f2> ", height="0.50"];
node0:f0 -> node1:f1;
node0:f2 -> node2:f1;
node1:f0 -> node4:f1;
node1:f2 -> node6:f1;
node4:f0 -> node7:f1;
node4:f2 -> node3:f1;
node2:f0 -> node5:f1;
node2:f2 -> node9:f1;
node9:f0 -> node8:f1;
node9:f2 -> node10:f1;
}
As you can see, each node has is divided into three parts. Each part has a name: <f0> for the first part, <f1> for the second part and <f2> for the third part. In order to call a given part of a node, the notation is node0:f0 - for the first part of node 0. The symbolic name has nothing to do with the displayed label. Also, as you may understand, a node part can be empty but still have a symbolic name.
Figure 2: Drawing a binary tree using Graphviz
The Graphviz code for creating our next example (figure 3) is the following:
digraph G
{
graph [rankdir = "LR" ];
node[fontsize = "14" style=bold];
# Table-field connection part.
BONUS [label="<tb> BONUS | sal | comm | ename | job"
shape = "record"];
DEPT [label="<tb> DEPT | loc | dname | deptno"
shape = "record"];
EMP [label="<tb> EMP | empno | ename | comm | mgr | hidedate | deptno | job"
shape = "record"]
CLIENT [label="<tb> CLIENT | sal | comm | ename | job"
shape = "record"];
CLERK [label="<tb> CLERK | sal | comm | ename | job"
shape = "record"];
ORDER [label="<tb> ORDER | sal | comm | ename | job"
shape = "record"];
FOO [label="<tb> FOO | sal | comm | ename | job"
shape = "record"];
# Tablespace decoration part.
TB_USERS [label="<tb> USERS" shape = "record" style=filled color="red"];
"node10" [label="<tb> DATA" shape = "record" style=filled color="red"];
TB_ADMIN [label="<tb> ADMIN" shape = "record" style=filled color="red"];
# TABLESPACE-table connection part.
BONUS:tb -> TB_USERS:tb;
DEPT:tb -> TB_USERS:tb;
CLIENT:tb -> TB_USERS:tb;
ORDER:tb -> TB_USERS:tb;
EMP:tb -> node10:tb;
CLERK:tb -> node10:tb;
FOO:tb -> TB_ADMIN:tb;
# Tablespace-to-tablespace connection.
TB_USERS -> "node10" -> TB_ADMIN;
TB_ADMIN -> TB_USERS;
label = "Out DataBase Schema";
fontsize=20;
}
This is a database schema, visualized with the help of Graphviz. The presented schema is simple; nevertheless you can still understand how elegant this is. By reading the Graphviz code you can understand that lines beginning with the # character are comments.
Figure 3: Creating a DB Schema using Graphviz.
I first have to tell you that if you decide to use the PixelGlow Graphviz version, you will not need the command line tools. PixelGlow's version will render the Graphviz code for you. Next, I should tell you that PixelGlow's Graphviz won Best Mac OS X Open Source Product and was runner-up in Best Product to Mac OS X in the 2004 Apple Design Awards.
The Mac OS X version supports native fonts, exporting to all Quicktime image formats, on-line viewing of the output, etc.
Figure 4: The PixelGlow Graphviz GUI
You may find it surprising, but the presented graph in figure 4 -that also shows the PixelGlow Graphviz GUI- uses the same Graphviz code that created figure 6! I only changed some Graphviz properties using the PixelGlow version and, as you can see, the new output is totally different!
Macintosh users have another option for rendering Graphviz files: OmniGraflle.
What is special about Omnigraffle is that it allows you to drag-and-drop a node or a group of nodes in order to rearrange your graph according to your needs. This is an excellent feature that allows you to fine tune your output.
Figure 5 shows Omnigraffle processing a Graphviz file. Again, you do not need the command line Graphviz tools to render Graphviz code when using Omnigraffle.
Figure 5: Using OmniGraffle with Graphviz files
When I was writing my eBook "Programming Dashboard Widgets", I wanted to visualize the structure of most of the presented Widgets. I decided to use Graphviz and I wrote the presented Perl script in order to automatically create the Graphviz code.
The Perl code for the script (I called it Wstruct.pl) is as follows:
#!/usr/bin/perl -w
#
# $Id: ch2.tex,v 1.1 2007/11/21 15:57:01 mtsouk Exp $
#
# This software is provided without any guarantees
# Please note that this is alpha code
#
# Programmer: Mihalis Tsoukalos
# Date: Thursday 16 March 2006
#
# For my eBook on Dashboard Widgets
#
# * * * Command line arguments
# * * * program_name.pl directory
#
# Please note that the directory argument must not contain
# an / at the end. The following is a correct example:
# program_name.pl /Library/Widgets/Weather.wdgt
# The following is a WRONG example:
# program_name.pl /Library/Widgets/Weather.wdgt/
#
# This graph does not include PNG files
#
use File::Find;
use File::Basename;
use strict;
my $directory="";
my %DIRECTORIES=();
die <<Thanatos unless @ARGV;
usage:
$0 directory
Thanatos
if ( @ARGV != 1 )
{
die <<Thanatos
usage info:
Please use exactly 1 argument!
Thanatos
}
# Get the file name
($directory) = @ARGV;
print <<START;
digraph Widget
{
size="16,6";
nodesep=0.05;
rankdir = LR;
rotate = 90;
edge[len=2];
node[style=filled, shape=record, fontsize=8];
node[height=0.20, width=0.20, color=gray];
START
find(\&create_graphviz, $directory);
print <<END;
}
END
exit 0;
#
#
sub create_graphviz
{
#print $_;
#print "\n";
# Skip ., .., .DS_Store and ALL png files
if ( $_ =~ /^\.\.?$/ || $_ =~ /^.DS_Store$/ || $_ =~ /png$/i )
{
# do nothing!
}
else
{
# If it is a directory, then...
if (-d $File::Find::name)
{
# Duplicates can only exist in directories.
# We must take care of it.
if ( ! defined($DIRECTORIES{$File::Find::name}) )
{
$DIRECTORIES{$File::Find::name} = 0;
create_node($File::Find::name);
}
}
# It is a file, then...
else
{
create_leaf(basename($File::Find::name));
}
}
}
#
#
sub create_node
{
my $path = shift;
print " \"".$path;
print "\"[label=\"".basename($path)."\"];\n";
# Create the connection with the parent node
print "// Create the connection with the parent node\n";
# If the $path is not equal to the $directory variable then,...
if ($path ne $directory)
{
print " \"".$path."\"";
print " -> \"".dirname($path)."\";\n";
if ( ! defined($DIRECTORIES{dirname($path)}) )
{
$DIRECTORIES{$path} = 0;
create_node(dirname($path));
}
}
else
{
# Create the node for the parent directory
# of $directory
#print " \"".$path;
#print "\"[label=\"".basename($path)."\"];\n";
}
}
sub create_leaf
{
my $file = shift;
my $size = 0;
# It is always a good idea to check twice!
if (-f $file)
{
# This finds the size of the file in bytes
$size = -s $file;
}
# add the byte symbol at the end of the byte number
$size .= "b";
# create the file node
print " \"".$file;
print "\"[label=\"".basename($file)." ".$size."\"];\n";
print " \"".$file."\"";
print " -> \"".dirname($File::Find::name)."\";\n";
if ( ! defined($DIRECTORIES{dirname($File::Find::name)}) )
{
$DIRECTORIES{dirname($File::Find::name)} = 0;
create_node(dirname($File::Find::name));
}
}
I am not going to explain you the perl code as this not the purpose of this article, but I will give you an example of its output. By running the perl script (./Wstruct.pl /Library/Widgets/Weather.wdgt) you will get the following Graphviz code:
digraph Widget
{
size="16,6";
nodesep=0.05;
rankdir = LR;
rotate = 90;
edge[len=2];
node[style=filled, shape=record, fontsize=8];
node[height=0.20, width=0.20, color=gray];
".identity"[label=".identity 2240b"];
".identity" -> "/Library/Widgets/Weather.wdgt";
"/Library/Widgets/Weather.wdgt"[label="Weather.wdgt"];
// Create the connection with the parent node
"Info.plist"[label="Info.plist 1078b"];
"Info.plist" -> "/Library/Widgets/Weather.wdgt";
"version.plist"[label="version.plist 451b"];
"version.plist" -> "/Library/Widgets/Weather.wdgt";
"Weather.css"[label="Weather.css 3371b"];
"Weather.css" -> "/Library/Widgets/Weather.wdgt";
"Weather.html"[label="Weather.html 4507b"];
"Weather.html" -> "/Library/Widgets/Weather.wdgt";
"Weather.js"[label="Weather.js 36590b"];
"Weather.js" -> "/Library/Widgets/Weather.wdgt";
"/Library/Widgets/Weather.wdgt/English.lproj"[label="English.lproj"];
// Create the connection with the parent node
"/Library/Widgets/Weather.wdgt/English.lproj" -> "/Library/Widgets/Weather.wdgt";
"InfoPlist.strings"[label="InfoPlist.strings 66b"];
"InfoPlist.strings" -> "/Library/Widgets/Weather.wdgt/English.lproj";
"localizedStrings.js"[label="localizedStrings.js 858b"];
"localizedStrings.js" -> "/Library/Widgets/Weather.wdgt/English.lproj";
"/Library/Widgets/Weather.wdgt/Images"[label="Images"];
// Create the connection with the parent node
"/Library/Widgets/Weather.wdgt/Images" -> "/Library/Widgets/Weather.wdgt";
"/Library/Widgets/Weather.wdgt/Images/Icons"[label="Icons"];
// Create the connection with the parent node
"/Library/Widgets/Weather.wdgt/Images/Icons" -> "/Library/Widgets/Weather.wdgt/Images";
"/Library/Widgets/Weather.wdgt/Images/Icons/moonphases"[label="moonphases"];
// Create the connection with the parent node
"/Library/Widgets/Weather.wdgt/Images/Icons/moonphases" -> "/Library/Widgets/Weather.wdgt/Images/Icons";
"/Library/Widgets/Weather.wdgt/Images/Minis"[label="Minis"];
// Create the connection with the parent node
"/Library/Widgets/Weather.wdgt/Images/Minis" -> "/Library/Widgets/Weather.wdgt/Images";
}
Figure 6 shows the graph that you will get after manually compiling the generated code using dot.
Figure 6: Using the Wstruct.pl perl script - an example.
Please note that the Wstruct.pl perl script does not include PNG files in its output. This was a design decision in order to avoid the busy output that some Widgets may have because they contained a plethora of PNG files. Also note that only regular files have their size in bytes next to them.
I hope that you find Graphviz both entertaining and interesting. I think that it is an exceptional piece of software that is very capable. Finally, there is plenty of useful material available in the web links provided, so you are bound to find some benefits through experimenting.
Books and Web Links
"A Technique for Drawing Directed Graphs". Gansner, E. R., Koutsofios, E., North, S. C. and Vo, K. IEEE Trans. Software Engineering, May 1993.
"An algorithm for drawing general undirected graphs". Kamada, T. and Kawai, S. Information Processing Letters, April 1989.
AT&T GraphViz site: http://www.research.att.com/sw/tools/graphviz
GraphViz Development Web Site: http://www.graphviz.org/
PixelGlow: http://www.pixelglow.com/graphviz/
Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms. Addison Wesley, 1974.
Michael Junger, Petra Mutzel (editors), Graph Drawing Software, Springer, 2003.
"GraphViz and C++", Platis N. and Tsoukalos M., C/C++ Users Journal, December 2005.
Mihalis Tsoukalos lives in Greece with his wife Eugenia and enjoys digital photography and writing articles. He is the author of the "Programming Dashboard Widgets" eBook. You can reach him at tsoukalos@sch.gr.
