Summary

this is a continuation of the previous post: Visualizing Data Structures With Dot. Part 1: Some Advanced Features of the Dot Language.

In this post, we write C code to output a graphviz file to render a quadtree data structure.

The Data Strucure Definition and a Caveat

The quadtree data structure from the last post was defined with two C structs.

// 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.
  int 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;
};

Since C has no built-in facilities for determining members of an unknown structure at run-time we will have to write a function which is specialized for QTREE_NODEs.

GCCXML can generate XML files describing the layout, members, and data types of C structures but arrays in C are problematic since they can declared explicitly or as pointers

int a[10];
int *b = malloc(sizeof(int)*10);

Without extra information, we have no way of knowing if a pointer member is an array or a link to another data object.

Ideally, we would like to write a single function which can accept a pointer to any C struct and write dot code to render its members and any other data objects which it refers to.

The Code

Our program will create a text file of dot source code which can then be run through dot program to produce a graphical version of any instance of a quadtree as defined above.

graphviz does have a C api but it is somewhat more cumbersome to use than the simple and direct method of writing text files and then passing them through dot.

Starting Point

The process is started with the function below

void print_to_dot(char *output_file_name, QTREE_NODE *qt)
{
  FILE *fout;
  if (!(fout = fopen(output_file_name, "w"))) {
    fprintf(stderr, "Failed to open: %s\n", output_file_name);
    exit(1);
  }
  fprintf(fout, "digraph quadtree {\n");
  print_to_dot_aux(fout, qt);
  fprintf(fout, "}\n");
  fclose(fout);
}

qt is a pointer to the node to output dot code for.

print_to_dot() writes the first line of dot code

diagraph quadtree {

then calls print_to_dot_aux() (auxiliary) to do the real work. Finally, the closing } is written and the output file is closed.

Printing a node and its children.

print_to_dot_aux() is declared as

void print_to_dot_aux(FILE *fout, QTREE_NODE *qt)

First, we must decide how a parent can refer to its children in the dot file. Since a pointer uniquely identifies a data object in C, we can label nodes with: N0xp where p is the hexadecimal value of the pointer to a node. The statement

printf("N%p", some_pointer);

can accomplish this.

All nodes will have a shape of record. The statement below will be executed for both leaf and nonleaf nodes

fprintf(fout, "  N%p [shape=record, label=\"", (void *) qt);

Leaf and nonleaf nodes also "cover" a rectangle so that will be printed in both cases as well

fprintf(fout, "{Rectangle:%d,%d,%d,%d|", qt->upper_left_x, qt->upper_left_y,
        qt->lower_right_x, qt->lower_right_y);

As an example, if the node that we are currently visiting is at address 0x10 (say) and its recangle has upper-left and lower-right corners (-128, 128) -- (-128,128) then what is printed is

  N0x10 [shape=record, label="{Rectangle:-128,128,-128,128|

Printing dot Code for Interior Nodes

If qt is a nonleaf node, then at least one its child pointers: ne_child, se_child, sw_child, and nw_child will be non-NULL. The if statement below will output the dot code for interior nodes:

  if (qt->ne_child || qt->se_child || qt->sw_child || qt->nw_child) {
    fprintf(fout, "{<ne>ne|<se>se|<sw>sw|<nw>nw}}\"];\n");
    fprintf(fout, "  N%p:ne -> N%p;\n", (void *) qt, (void *) qt->ne_child);
    fprintf(fout, "  N%p:se -> N%p;\n", (void *) qt, (void *) qt->se_child);
    fprintf(fout, "  N%p:sw -> N%p;\n", (void *) qt, (void *) qt->sw_child);
    fprintf(fout, "  N%p:nw -> N%p;\n", (void *) qt, (void *) qt->nw_child);
    print_to_dot_aux(fout, qt->ne_child);
    print_to_dot_aux(fout, qt->se_child);
    print_to_dot_aux(fout, qt->sw_child);
    print_to_dot_aux(fout, qt->nw_child);
  }

The last four lines of the if statement above will print the children of qt to the output file.

If the Northeast, Southeast, Southwest, and Northwest children of qt have addresses 0x111, 0x222, 0x333, and 0x444 respectively, then the the total output would be

N0x10 [shape=record, label="{Rectangle:-128,128,-128,128|{<ne>ne|<se>se|<sw>sw|<nw>nw}}"];
N0x10:ne -> N0x111;
N0x10:se -> N0x222;
N0x10:sw -> N0x333;
N0x10:nw -> N0x444;

Printing dot Code for Leaf Nodes

The data_list member of QTREE_NODE points to the first element of a linked-list of data item stored in leaf nodes. The C code to handle leaf nodes is

if (!qt->data_list) {
  fprintf(fout, "{No Data}}\"];\n");
} else {
  QTREE_DATA_ITEM *lp;
  fprintf(fout, "{");
  for (lp = qt->data_list; lp; lp = lp->next) {
    fprintf(fout, "\\\"%s\\\" (%d, %d)%s", lp->data, lp->x, lp->y,
            lp->next ? "|" : "");
  }
  fprintf(fout, "}}\"];\n");
}

If qt is a leaf node containing the data

data x y
"X3" -64 -64
"X1" -64 -64
"X0" -64 -64
"X2" -64 -64

Then what is printed is

N0x10 [shape=record, label="{Rectangle:-128,-1,-1,-128|
       {\"X3\" (-64, -64)|
        \"X1\" (-64, -64)|
        \"X0\" (-64, -64)|
        \"X2\" (-64, -64)}}"];

The long line was broken for clarity.

Complete Function

The full code for print_to_dot_aux() is

void print_to_dot_aux(FILE *fout, QTREE_NODE *qt)
{
  fprintf(fout, "  N%p [shape=record, label=\"", (void *) qt);
  fprintf(fout, "{Rectangle:%d,%d,%d,%d|", qt->upper_left_x, qt->upper_left_y,
          qt->lower_right_x, qt->lower_right_y);
  if (qt->ne_child || qt->se_child || qt->sw_child || qt->nw_child) {
    fprintf(fout, "{<ne>ne|<se>se|<sw>sw|<nw>nw}}\"];\n");
    fprintf(fout, "  N%p:ne -> N%p;\n", (void *) qt, (void *) qt->ne_child);
    fprintf(fout, "  N%p:se -> N%p;\n", (void *) qt, (void *) qt->se_child);
    fprintf(fout, "  N%p:sw -> N%p;\n", (void *) qt, (void *) qt->sw_child);
    fprintf(fout, "  N%p:nw -> N%p;\n", (void *) qt, (void *) qt->nw_child);
    print_to_dot_aux(fout, qt->ne_child);
    print_to_dot_aux(fout, qt->se_child);
    print_to_dot_aux(fout, qt->sw_child);
    print_to_dot_aux(fout, qt->nw_child);
  } else {
    if (!qt->data_list) {
      fprintf(fout, "{No Data}}\"];\n");
    } else {
      QTREE_DATA_ITEM *lp;
      fprintf(fout, "{");
      for (lp = qt->data_list; lp; lp = lp->next) {
        fprintf(fout, "\\\"%s\\\" (%d, %d)%s", lp->data, lp->x, lp->y,
                lp->next ? "|" : "");
      }
      fprintf(fout, "}}\"];\n");
    }
  }
}

The complete program to create and search quatree structures can be found in My github repo for this blog

Example output

If we have a quadtree given by

Addr Rectangle NE Child SE Child SW Child NW Child Data (x,y)
0x010 -128, 128, 128, -128 0x0d0 0x110 0x150 0x190
0x0d0 0, 128, 128, 0
0x110 0, -1, 128, -128 0x2d0 0x310 0x350 0x390
0x2d0 64, -1, 128, -64
0x310 64, -65, 128, -128 "C" ( 96, -96)
0x350 0, -65, 63, -128
0x390 0, -1, 63, -64 "B" ( 32, -32)
0x150 -128, -1, -1, -128 "X3" (-64, -64), "X1" (-64, -64), "X0" (-64, -64), "X2" (-64, -64)
0x190 -128, 128, -1, 0 "A" (-64, 64)

The generated dot code is

digraph quadtree {
  N0x010 [shape=record,
          label="{Rectangle:-128,128,128,-128|{<ne>ne|<se>se|<sw>sw|<nw>nw}}"];
  N0x010:ne -> N0x0d0;
  N0x010:se -> N0x110;
  N0x010:sw -> N0x150;
  N0x010:nw -> N0x190;
  N0x0d0 [shape=record, label="{Rectangle:0,128,128,0|{No Data}}"];
  N0x110 [shape=record,
          label="{Rectangle:0,-1,128,-128|{<ne>ne|<se>se|<sw>sw|<nw>nw}}"];
  N0x110:ne -> N0x2d0;
  N0x110:se -> N0x310;
  N0x110:sw -> N0x350;
  N0x110:nw -> N0x390;
  N0x2d0 [shape=record, label="{Rectangle:64,-1,128,-64|{No Data}}"];
  N0x310 [shape=record, label="{Rectangle:64,-65,128,-128|{\"C\" (96, -96)}}"];
  N0x350 [shape=record, label="{Rectangle:0,-65,63,-128|{No Data}}"];
  N0x390 [shape=record, label="{Rectangle:0,-1,63,-64|{\"B\" (32, -32)}}"];
  N0x150 [shape=record, label="{Rectangle:-128,-1,-1,-128|
                                {\"X3\" (-64, -64)|
                                 \"X1\" (-64, -64)|
                                 \"X0\" (-64, -64)|
                                 \"X2\" (-64, -64)}}"];
  N0x190 [shape=record, label="{Rectangle:-128,128,-1,0|{\"A\" (-64, 64)}}"];
}

and the rendered version is dot-c-test.png

Next

In the final post, we will explore some techniques for generating dot files from Java data structures. Java has a Class and Field objects which permit us to write generic code to render most data structures.