Drawing DAG’s
I have been using DAG’s for well over 20 years now. As a compiler designer, until about 5 years ago, DAG’s were not only my bread and butter, they were my knife and plate too. I learned to picture them, inside and outside my head. But, after all these years, the latter part still poses some challenges.
It’s time to scratch that itch.
DAG
You may wonder: what’s a DAG? ‘DAG’ is short for directed acyclic graph. It’s a network where connections have direction (forward), and there’s no going back. They are not like social networks “we are friends", but more like family trees, parent and child. The family tree also satisfies the acyclic property: you cannot be your own ancestor. It actually does not satisfy the tree property: you can have a common ancestor through your father and mother. Which means your family tree is not a tree at all. It’s a family DAG.
DAG’s are used in a large variety of applications, mostly related to software engineering. You can find them:
- in dependency systems like pip, npm, make, or even Gantt charts;
- in artificial intelligence: machine learning, feedfoward neural networks, and causal reasoning;
- in cryptocurrency;
- in certain data flow systems, like compilers, Apache Spark, Apache airflow, databricks;
- and more.
With so many uses for DAG’s, there is a need for visualizing them.
For my current project I’m looking for good DAG visualization, for DAG’s without edge labels and with long node labels, preferably in a jupyter notebook and interactive, but I need to be able to save the image to a file too.
Dot
The go-to solution for drawing DAG’s 5 years ago was graphviz’s dot tool, and to a large extent, it still is.
It does work quite well, better than most, but …
- I really dislike asking users to install another executable as some packages do (e.g.: graphviz for python, pydot, viz.js). It makes a messy install procedure.
- It doesn’t really integrate well with other visualization solutions, let alone interactive solutions.
- When graphs get really large, the end-result is still not very readable.
And, I am sorry to say, graphviz is at risk of becoming unmaintained:
This project has only 3 of its founders remaining as volunteer maintainers, and support is limited and may end soon. If you can help fund to a more formal foundation to continue this project, please contact north on graphviz org.
I sincerely hope someone will do this.
Not dot
But if not dot, what else? The problem with many other popular graph visualization tools, like cytoscape and gephi, is that they are focused on undirected graphs, like social networks. They tend to use things like spring layouts, or other schemes that work well there, but that don’t really work well for DAG’s.
You see, DAG’s, like flow graphs and unlike generic directed graphs, have a start and a dominant direction. All “arrows” point in the same direction. Any visualization should emphasize or utilize this.
By their nature, spring layouts put emphasis on edge length, which is not that important for DAG’s.
As my interest is in jupyter notebooks, we need to look at what’s available for Python and JavaScript.
Python
The Python package to use if you want to do anything with graphs is networkx. It is an excellent package for graph processing, directed and undirected. And ‘lo and behold: it can draw graphs. Unfortunately, for DAG’s the output is abysmal, see the example below. I’ll spare you the Unix lineage graph, it’s a lot worse.
This example uses matplotlib, the major visualization package for Python. Two other visualization packages of note are plotly and bokeh. Both support networkx, and where plotly uses cytoscape for layout, bokeh has its own.
DAG drawing in any of these visualizers would be wonderful as they are used from web servers to jupyter notebooks, but they only provide decent support for undirected graphs.
This seems to be a dead end. Let’s look at JavaScript.
JavaScript
Although any JavaScript solution would require some work to get it nicely integrated in a jupyter notebook, we would need to develop something at this stage anyway, so better find out what we can use.
There’s an abundance of visualization solutions in JavaScript, most focus on various forms of charts, but some do offer graph visualization. Although there are a number of options for undirected graphs, I was able to find two for DAG’s: D3-DAG, using the well known D3js, and dagre which can be used with a number of the visualization backends.
Then there’s mermaidjs, which can draw flow charts, but I think is not well suited for anything else. You could also draw DAG’s by abusing Sankey diagrams, like GitLab. It kind of works, I guess.
D3-Dag is under active development (dated June 2021) and while not as extensive as dagre, offers pretty good visualizations, like this one. The Unix lineage as drawn below is nice, but it required more hand work than I’d like to get it into this state.
I had to do a bit of trial-and-error work to set the bubble size and the space between bubbles correctly. I would rather leave that to the visualizer. Although the coloring scheme is hand-work too, that’s probably easy to automate, and in this case I could copy the code from one of the examples.
Overall, if you just want a quick DAG visualization, D3-DAG is probably not for you.
Dagre seems to deliver pretty good quality visualizations, approaching the quality of dot. The drawing of the Unix lineage below was easy to produce and, although the edge to “PDP-11 SysV” is a bit confusing, it’s quite readable.
I’m not sure whether it’s still being maintained, the last release of dagre-d3 was in 2017, but currently it is the best option for DAG drawing, if you don’t want to use dot.
Dagre really is the only package I could use so far. But there’s this one DAG visualization that I miss. One that works very well for it’s context and, I was honestly surprised to find, none of the above packages offer.
Git
Have you ever looked at a git commit graph?
That, dear reader, is a DAG. It’s readable, even for large graphs. It may not suffice for all DAG visualization needs, but I think it works for plenty of situations. It would for mine.
DAGVIZ
Now, I’m not a DAG drawing expert, but I can create a DAG visualization like the one used by git. That’s just a simple scheduling problem.
I made a small Python package on top of networkx to do just that. Looking at the Unix lineage it draws, I can see there’s room for improvement, the ordering of the rows is suboptimal, and it would be nice if you could order rows and columns interactively, but still it’s a useful DAG visualization option to have.
On top of this, it also provides DAG visualization for jupyter notebooks using dagre.
It’s called DAGVIZ.
