Using dot to Help Visualize Data Structures Part 2

January 19, 2020 - 4 minutes read - 646 words

In a previous post, I demonstrated how we can create simple text-based files that represent directed graphs and feed them to dot, a program that can create directed graphs as PNG or PDF output. We wanted to add this capability so that the “thinking” of the binary search tree (BST) was visible in a way that helps us learn more about this important data structure.

I’ve cleaned up the ideas in that post and have shared them as a repository. The branch 01-add-graphviz-printer has code and tests (npm test) to do what was described in the previous post. Emit the dot source file by running npm -s run dev (-s prevents NPM output from going into our dot source file and messing it up).

At the end of my previous post, however, I teased that it’d be really great to be able to visualize the logic behind a BST node deletion operation. By extending the code on 01-add-graphviz-printer, I was able to demonstrate what deletion of a BST node looks like.

Here’s a preview:

Graphviz drawing showing a BST node’s deletion

After the jump I show the code that made this possible.

Code

In the previous emitter code:

1
2
3
4


const BST_SOURCE = shuffledRange(1, 100)
const randomValue = Math.floor(Math.random() * BST_SOURCE.length + 1)
const tree = new BST(BST_SOURCE)
tree.printBFS()

In this code, we make a slight extension:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


const BST_SOURCE = shuffledRange(1, 100)
const randomValue = Math.floor(Math.random() * BST_SOURCE.length + 1)
const tree = (new BST(BST_SOURCE))
tree.printBFS({
  ...graphVizPrintHelper,
  pre: (...args) => {
    graphVizPrintHelper.pre(...args)
    console.log(deletionDigraphDisplayLogic(randomValue))
  }
})

The printBFS method takes a printer helper Object when we call it and uses, as default, graphVizPrintHelper. As BST#printBFS does a Breadth-First Search, it delegates how to do the presentation to functions provided within the helper. This allows us to plug in whatever kind of printer would be helpful (maybe an HTML- or LaTeX-formatting printer is a future option).

Helpers provide a pre, per, and post function. This is “What goes at the start”, “What I print for each pair”, and “What goes at the end.” We can see this in the simple graphVizPrintHelper code.

Thus, in lines 4-9, above, we’re going pass print_helpers a new Object that’s made from destructuring graphVizPrintHelper and overwriting its pre function. We’re going to add styling data to the top of our source to make the deletion logic “pop.”

We wrap that deletion logic inside of a function declared (above) called deletionDigraphDisplayLogic which, sensibly, needs to know which value we’ve randomly chosen to delete. The remainder of the heavy lifting then comes into two tasks:

Do the BST pseudo-deletion logic in a way that prints out Graphviz source code (code). This method does not actually perform the deletion. Instead, it shows what deletion should do. It’s a simple matter to add the code to do the deletion from this point. I leave that step to the reader. Here are call-outs for specific cases of the BST:
Keep the code clean enough to read. I chose to separate presentation configuration into a “style” object called GRAPHVIZ_CONFIG (code).

Conclusion

With this, we’ve built out an extensible framework for styling and documenting logic within binary search trees. Because we’ve always worked from a place where we had rich visual feedback, we’ve always been able to reason about extending our tools because we could see what’s going on.

Graphviz is a powerful tool in surfacing what code is doing. Whenever you find yourself getting output from a program that requires YOU to move too close to it (this BST code’s world of opaque left and right references), take the time to help it tell YOU what’s going on! The dot program is a powerful ally!