Photo of David Winter

david winter

Graphviz - for drawing directed graphs

This semester at University, I’m taking ‘Compiler Design & Techniques’ as a module. The second coursework involves drawing Finite State Machines diagrams that represent regular expressions. Rather than using a word processor to draw these diagrams with a rather untidy look about them, I went in search of a tool that’d help me produce high quality drawings. I’d heard that Latex was good for mathematical diagrams, but that seemed like overkill as I only wanted the diagrams, not a whole new document syntax to learn.

I come across Graphviz. Open source and available on near enough all platforms–Mac, Linux and Windows. Using a very simple syntax, you create dot files and then using the dot tool, you can generate PNG images of your diagrams.

Here is an example dot script:

digraph my_fsm {
    label = "ab*(cd)+|b";
    rankdir = LR;
    node [shape = doublecircle]; 3 4;
    node [shape = circle];
    0 -> 1 [label = "a"];
    1 -> 1 [label = "b"];
    1 -> 2 [label = "c"];
    2 -> 3 [label = "d"];
    3 -> 2 [label = "c"];
    0 -> 4 [label = "b"];
}

Following is an explanation of the above script:

  1. I’m declaring the graph as a directed graph with digraph.
  2. my_fsm is just the name I’ve given the graph. This can be anything.
  3. I add a label to the graph which holds the regular expression that I’m drawing. This isn’t required, but just helps by giving it a title.
  4. rankdir specifies the direction of the diagram. I’m specifying ’left to right’ with LR.
  5. So that I can differentiate between accepting states and normal states, I’m declaring that nodes 3 and 4 will have a double circle around them.
  6. For all other nodes, I just want to use the normal circle shape.
  7. Lastly, I declare the nodes and their edges. Also, I add a label to each edge.

Once you save the file, you can run it through the dot program using the following command:

dot my_file.dot -Tpng -o my_fsm.png

You’ll need to check where dot was installed. With the Mac installer package it is installed to /usr/local/graphviz-2.12/bin/dot, so you’ll need to modify the above command to reflect the correct location.

The outputted file, my_fsm.png in this example, should result in something that looks like the one below.

Finite State Machine Example

A very handy tool indeed. There is a PDF guide on all the commands available. Of which, I’m next going to look for how to space the graph out a bit more as it’s a little squashed at the moment.

Hope this helps.