Summary

This is a continuation of the previous post: Visualizing Data Structures With Dot. Part 0: The Dot Language.

In this post, we will explore some features of the dot language that make it particularly suited to drawing data structures. Our goal is to write a program to generate dot code to draw quadtree data structures

Problem : Several Fields in an Object or Structure With Outgoing Links.

In many cases, a drawing of the outgoing links of a data structure might not be so obvious as they were with the binary tree of the last post. For example, suppose that we have have a quadtree where nodes are defined (in C) as

// Each terminal node in a quadtree
// contains a list of data items.
// In this case, the data are simple strings.
typedef struct _QTREE_DATA_ITEM QTREE_DATA_ITEM;
struct _QTREE_DATA_ITEM {
  double x, y;
  char *data;
  QTREE_DATA_ITEM *next;
};

typedef struct _QTREE_NODE QTREE_NODE;
struct _QTREE_NODE {
  // Rectangle that this node covers.
  double upper_left_x, upper_left_y,
         lower_right_x, lower_right_y;
  QTREE_NODE *ne_child, *se_child,
             *sw_child, *nw_child;
  QTREE_DATA_ITEM *data_list;
};

And we have the data on a 256 ⨉ 256 grid which is centered at (0,0).

advanced-dot-qtree-grid-shadow.png

Addr Rectangle Node Type ne se sw nw data
0x01 -128,128,128,-128 nonleaf 0x02 0x03 0x04 0x05
0x02 0,128,128,0 leaf no data
0x03 0,0,128,-128 nonleaf 0x06 0x07 0x08 0x09
0x04 -128,0,0,-128 leaf w/data "D"
0x05 -128,128,0,0 leaf w/data "A"
0x06 64,0,128,-64 leaf no data
0x07 64,-64,128,-128 leaf w/data "C"
0x08 0,-64,128,-128 leaf no data
0x09 0,0,64,-64 leaf w/data "B"

How can dot be used to display the internal data structure in a useful way?

Solution : Records and Ports

We would like our nodes to be rendered by dot in a fashion similar to what one would find in a data structures textbook. For example

advanced-dot-node-shadow.png

There are three elements that we need to cover:

  • Labels
  • Records
  • Ports

Labels

Labels are simply text which is displayed inside of a node. For example

digraph smalltree {
  ordering=out;
  0 [label="parent"];
  1 [label="child one"];
  2 [label="child two"];
  0 -> 1;
  0 -> 2;
}

If no label is supplied, then dot will label a node with the node name used to build the graph. In the tree above, the node names are: 0, 1, and 2.

advanced-dot-small-tree-shadow.png

Records

Records are a special node shape that allow labels to be separated by vertical and horizontal lines. When records are used, the labels typically represent fields in some structure. Here is an example

digraph record {
  node0 [shape=record,label="field0|field1|field2"];
  node0 -> node1;
}

advanced-dot-record0-shadow.png

Fields can be stacked vertically by surrounding them with curly brackets.

digraph record {
  node0 [shape=record,label="{field0|field1|field2}"];
  node0 -> node1;
}

advanced-dot-record1-shadow.png

If you wish for some fields to be stacked vertically and others to appear next to each other horizontally, use nested curly brackets.

digraph record {
  node0 [shape=record,label="{field0|{field1|field2}}"];
  node0 -> node1;
}

advanced-dot-record2-shadow.png

The curly brackets should be taken to mean: "toggle between vertical and horizontal placement".

digraph record {
  node0 [shape=record,label="{field0|{field1|field2|{field4|field5}}}"];
  node0 -> node1;
}

advanced-dot-record3-shadow.png

Ports

If a particular field contains an outgoing link, then we would like dot to draw the link at the same location as the field. The code below demonstrates the problem that ports solve

digraph port {
  ordering=out;
  root [shape=record,label="link0|link1|link2|link3|link4"];
  root -> child0;
  root -> child1;
  root -> child2;
  root -> child3;
  root -> child4;
}

advanced-dot-port0-shadow.png

In this drawing, it is not obvious which fields contain which links.

One solution is to label the outgoing links themselves

digraph port {
  ordering=out;
  root -> child0 [label="link0"];
  root -> child1 [label="link1"];
  root -> child2 [label="link2"];
  root -> child3 [label="link3"];
  root -> child4 [label="link4"];
}

advanced-dot-port1-shadow.png

Ports are labeled fields which can be used to specify an origin point for a link. Ports are defined inside of a node label and are written in angle brackets. Ports can be referenced in links with the syntax: sourceNode:port -> targetNode

digraph port {
  ordering=out;
  root [shape=record,label="<L0>link0|<L1>link1|<L2>link2|<L3>link3|<L4>link4"];
  root:L0 -> child0;
  root:L1 -> child1;
  root:L2 -> child2;
  root:L3 -> child3;
  root:L4 -> child4;
}

advanced-dot-port2-shadow.png

Example

Armed with records and ports, we can now tackle the quadtree from the beginning of this post. Although this code is monotonous our ultimate goal is to have it generated by a program.

digraph quadtree {
  N0x01 [shape=record,
         label="{Rectangle:-128,128,128,-128|{<ne>ne|<se>se|<sw>sw|<nw>ne}}"];
  N0x01:ne -> N0x02;
  N0x01:se -> N0x03;
  N0x01:sw -> N0x04;
  N0x01:nw -> N0x05;
  N0x02 [shape=record,
         label="{Rectangle:0,128,128,0|No Data}"];
  N0x03 [shape=record,
         label="{Rectangle:0,0,128,-128|{<ne>ne|<se>se|<sw>sw|<nw>ne}}"];
  N0x03:ne -> N0x06;
  N0x03:se -> N0x07;
  N0x03:sw -> N0x08;
  N0x03:nw -> N0x09;
  N0x04 [shape=record,
         label="{Rectangle:-128,0,0,-128|{Data:\"D\"|Data (x,y):-64,-64}}"];
  N0x05 [shape=record,
         label="{Rectangle:-128,128,0,0|{Data:\"A\"|Data (x,y):-64,64}}"];
  N0x06 [shape=record,
         label="{Rectangle:64,0,128,-64|No Data}"];
  N0x07 [shape=record,
         label="{Rectangle:64,-64,128,-128|{Data:\"C\"|Data (x,y):96,-96}}"];
  N0x08 [shape=record,
         label="{Rectangle:0,-64,128,-128|No Data}"];
  N0x09 [shape=record,
         label="{Rectangle:0,0,64,-64|{Data:\"B\"|Data (x,y):32,-32}}"];
}

advanced-dot-quadtree2-shadow.png

Next

In the next post, we will explore some techniques for generating dot files in C.