Visualizing Data structures With dot. Part 0: the dot Language.

The Problem

Visualizing data structures can be a great aid in debugging. Unfortunately most development environments don't have the capability to display linked data in graphical form. One notable exception is the GNU Data Display Debugger (http://www.gnu.org/software/ddd/).

A Solution

In this four-part series, we will explore a few simple techniques for drawing data structures using the dot language.  

• Part 0: The dot Language.
• Part 1: Some Advanced Features of the dot Language.
• Part 2: Visualizing Data Structures in C.
• Part 3: Visualizing Data Structures in Java.

dot is part of the popular graphviz suite of tools (http://graphviz.org/).

All of the source code used in this blog post can be found at https://bitbucket.org/todd_k_fisher/problem-solved-blog/overview. I have placed the Emacs org-mode file used to create this post there as well.

Basics of the dot Language

dot is used to draw directed graphs which have a (mostly) hierarchical structure. The language is easily understood by example. A binary tree might be specified as 

file: example0.dot

digraph bintree {
  10 -> 5;
  10 -> 15;
  5  -> 2;
  5  -> 8;
  2  -> 1;
  2  -> 3;
  8  -> 6;
  8  -> 7;
  15 -> 13;
  15 -> 20;
}

Edges are given with: startNode -> endNode. Use the dot command to render this to an SVG file

dot -Tsvg example0.dot -oexample0.svg

The result can be viewed in your browser

Simple binary tree (from example0.dot)

dot can also handle general graph structures. Here is a non-hierarchical graph

file: cycle.dot

digraph cycle {
  1 -> 2 -> 3 -> 4 -> 1;
}

Cyclic graph
(from cycle.dot)

Care must be used if the ordering of children is important. Had the two children of node 8 been mistakenly reversed in the source file as indicated by the red lines

file: example1.dot

digraph bintree {
  10 -> 5;
  10 -> 15;
  5  -> 2;
  5  -> 8;
  2  -> 1;
  2  -> 3;
  8  -> 7;
  8  -> 6;
  15 -> 13;
  15 -> 20;
}

the result would not be a correctly rendered binary tree

Incorrectly drawn binary tree
(from example1.dot)

To remedy this, set the ordering to match the order listed in the source file with the code: ordering=out and be sure to list the children of each node from lowest to highest.

Node Shapes

The default shapes of nodes in dot are ellipses. Differently-shaped nodes can be drawn by writing the node name followed by the shape as in

file: example2.dot

digraph bintree {
  ordering=out;
  1  [shape=rectangle];
  3  [shape=rectangle];
  6  [shape=rectangle];
  7  [shape=rectangle];
  13 [shape=rectangle];
  20 [shape=rectangle];
  10 -> 5;
  10 -> 15;
  5  -> 2;
  5  -> 8;
  2  -> 1;
  2  -> 3;
  8  -> 6;
  8  -> 7;
  15 -> 13;
  15 -> 20;
}

The tree now looks like

Binary tree with
rectangular leaves.
(from example2.dot)

The location of the [shape = rectangle] lines in the source file is unimportant.

Colors

Nodes can be filled or outlined with a particular color. Let's outline the interior nodes in our tree brown and fill in the leaves light green. To do this, set the color attributes of each node.
For outline colors write: color = brown.
For color fills write: color = palegreen,style = filled.
Let's color the edges in the tree brown as well.
Colored edges should be followed with [color = brown]

file: example3.dot

digraph bintree {
  ordering=out;
  1        [shape=rectangle, color=palegreen, style=filled];
  3        [shape=rectangle, color=palegreen, style=filled];
  6        [shape=rectangle, color=palegreen, style=filled];
  7        [shape=rectangle, color=palegreen, style=filled];
  13       [shape=rectangle, color=palegreen, style=filled];
  20       [shape=rectangle, color=palegreen, style=filled];
  10       [color=brown];
  5        [color=brown];
  2        [color=brown];
  8        [color=brown];
  15       [color=brown];
  10 -> 5  [color=brown];
  10 -> 15 [color=brown];
  5  -> 2  [color=brown];
  5  -> 8  [color=brown];
  2  -> 1  [color=brown];
  2  -> 3  [color=brown];
  8  -> 6  [color=brown];
  8  -> 7  [color=brown];
  15 -> 13 [color=brown];
  15 -> 20 [color=brown];
}

Colored binary tree.
(from example3.dot)

Next

In the next part of this series, we will explore some more advanced features of dot:

• Record structures with labeled fields.
• Subgraphs.