POSTS
Using dot to Help Visualize Data Structures Part 2
BlogIn 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:
After the jump I show the code that made this possible.
Code
In the previous emitter code:
|
|
In this code, we make a slight extension:
|
|
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!