Using graphviz to draw graphs

Many domains of applied computer science and numerics are engaged with graph theory. So if you participate in a lecture or seminar about theoretical informatics, you will often work with deterministic or nondeterministic finite-state machines. Or if you talking about Complexity theory, you will often hear of graph problems like Travelling salesman problem (eg. TSP) or the Clique problem.

This is all ver interesting, but you often get in trouble if you are looking for an easy to use library or software tool to create graphics from such graphs. As I create all worksheets, presenations and handouts using Latex (not PdfLatex), I was looking for an easy to use library that creates the graphics based on a very simple grammar. So I came first up with the Latex package pstricks (I will cover this in a future post), but it was to complex for my needs and I was locking for something which I could easily integrate into software projects. And after some hours of googling I found graphviz.

Graphviz is an open source software that uses structured information, a simple grammar, called DOT language, to visualize graphs, diagrams or networks. So it is a perfect tool to create graphics for any kind of presentation to visualize computer networks, deterministic or nondeterministic finite state machines, interface specifications, entity relationship models (ERMs) and flow or timing charts. Although it supports various output formats like *.jpg, *.svg, *.pdf or *.eps, which is perfect if you are working with Latex. Furthermore there are thousands of options that could be used to improve your graphics. So you could change the colors or shapes of a diagramm, adjust the line styles, add a legend or hyperlink and change the arrow or node style.

To install graphiz on an Ubuntu system just run the command below:

sudo apt-get install graphviz

To demonstrate the usage of graphviz I dig out an old exercise of my computer and network security course. The task was to draw a keyword tree for the strings “lol”, “loy”, “orly”, “yolo” and “yoyo”. So I created the keyword tree shown in the graphic below.

The definition that produces this output is straight forward. See the code below.

digraph keyword_tree {
    rankdir=LR;
    size="8,5"

    node [shape = circle];
    0 -> 1 [ label = "L" ];
    1 -> 2 [ label = "O" ];
    2 -> 3 [ label = "L" ];
    2 -> 4 [ label = "Y" ];

    0 -> 5 [ label = "O" ];
    5 -> 6 [ label = "R" ];
    6 -> 7 [ label = "L" ];
    7 -> 8 [ label = "Y" ];

    0 -> 9 [ label = "Y" ];
    9 -> 10 [ label = "O" ];
    10 -> 11 [ label = "L" ];
    11 -> 12 [ label = "O" ];
    10 -> 13 [ label = "Y" ];
    13 -> 14 [ label = "O" ];
}

The following command produces the corresponding *.jpg file.:

dot -.jpg graph.gv -o keyword_tree.jpg

If you are working with keyword trees you often add fallback links to avoid unnecessary parsing steps. You could imagine this fallback links as crosslinks between to nodes. To visualize this links I add them in another color. Therefore just add the following lines of code at the end of the graph specification.

digraph keyword_tree_linked {
    ...

    2 -> 5 [color = dodgerblue3];
    4 -> 9 [color = dodgerblue3];
    7 -> 1 [color = dodgerblue3];
    8 -> 9 [color = dodgerblue3];
    12 -> 2 [color = dodgerblue3];
}

This will produce the following output:

And since I talked so much about deterministic or nondeterministic finite state machines, here is another example that produces a really nice looking graph with a single dot as entry point and an double circled node as accepting state.

digraph finite_state_machine {
    rankdir=LR;
    size="8,5"

    node [shape = doublecircle]; s3;
    node [shape = point ]; start;

    node [shape = circle];
    start -> s1;
    s1  -> s1 [ label = "a" ];
    s1  -> s2  [ label = "b" ];
    s2 -> s2  [ label = "a" ];
    s1 -> s3 [ label = "b" ];
    s2 -> s3 [ label = "b" ];
}

Hope you enjoyed this short overview. Stay tuned for the upcoming pstricks overview.