This is a cool example of how specializing a generic algorithm to a specific subspace can yield much better results. This is quite often the case in my experience, but we often don't bother utilizing properties that are specific to our problem space, and just apply the generic algorithm out of convenience (and because it is often good enough)
Came here to say this, but with caveats. The particular domain has extra properties that allow their "stupider" algorithm to work better in their case. But a general graph drawing system has to deal with the inherent generality of the domain.
Usually there is a good middle ground: heuristic analysis of the input to see if it fits well with special-case "stupid and fast" algorithms, and sophisticated optimizations that are the fallback and work for everything and come with guarantees.
This is a concept I'm working around with Microdiagram (microdiagram.com) prototype.
i.e. having a general purpose diagram/graph layout is hellishly difficult, but most of the diagrams/charts follow much simpler rules, thus it's much easier to have N languages, each for 1 type of diagram, than 1 language for N types of diagrams.
Nice work! The examples look better than the Graphviz output, indeed. This is a good example of how you can always beat a long-developed, generic tool by specializing for a much narrower use case.
I have struggled with code to diagram tools for a while [mermaid and graphviz], and usually return to figjam when I need the readabilty and aesthetics.
graph-viz is MASSIVE and a binary. mermaid requires the browser's svg rendering system to work. I just need something that builds diagrams from description easily ...
This is great. I've been trying to generate diagrams for HDL hierarchies and neither Graphviz nor ELK can do a remotely good job. In fact I've never got good results from Graphviz for any graphs over a handful of nodes. I think it just isn't actually very good. But it has such huge mindshare even if there was a better option I wouldn't be able to find it.
I would love to see this evolve into a more general purpose control flow graph viewer - pretty much any language implementation would find it a great debugging tool. it's probably most of the way there already.
We looked at using Graphviz, but the copyleft nature of Graphviz license (Eclipse Public License) means that this will never be allowed in our company's software.
It used to be a that the barrier of entry of creating a new tool was high - so we had to use popular pieces of software, often stretching them, or writing plugins (that had their own constraints).
Now it is often easier to write from scratch a new piece of software, for which with have full control.
We can stand on the shoulders of giants - not just "a giant".
This is a great write up and thank you to the author! Just a note that graphviz dot is not purely Sugiyama’s, there is a paper on the site that details the actual implementation.
Also judging from the final two images (dot vs iongraph for the same large graph) it’s clear that dot is optimized for minimal area where iongraph does not. That’s the trade off. The author claims one is more easy to navigate than the other, I think that’s debatable.
Ultimately I found that visualizing large graphs is rarely helpful in practice; they can certainly look nice for some well defined graphs, but I rarely saw well defined graphs in the wild. Ymmv but maybe some would agree?
Layout is one of those things humans do so easily and intuitively, yet you couldn't write an easy algorithm for it. I wonder if there's potential to use gen ai to achieve human like results. Anyone has any thoughts on feasibility and complexity of such an approach?
D2 "should" handle most cases OP was annoyed about. Its written in Go, so its really fast too. I never had to wait for it to finish, but that said i never produced huge diagrams that i could imagine a compiler would.
The greatest thing about Graphviz is indeed the dot language. A nice thing about using dot is that the graph definition is *portable among all applications that support dot*.
Dot is such a simple and readable format (particularly if using the basic features). Thus, it can make a ton of sense to define graphs in strict dot, even if you will be rendering with another tool than Graphviz.
These days, there are other popular options, too -- Mermaid, etc, as TFA indicates. Nonetheless, Graphviz/dot will remain for the long haul, IMO, because dot is so, so good.
So, you need Graphviz for its syntax definitions primarily, and because it is a standard that could be recognized/run anywhere.
For those who are interested, the Will Evans course on graph drawing [1] covers a lot of cool graph drawing algorithms. Graph drawing is very interesting and many applications get it wrong. I once contributed [2] some small bugfixes to the Dot lexer for the Open Graph Drawing Framework, which has fast implementations of some amazing graph drawing algorithms, and my experience is that the OGDF draws graphs vastly better than the various algorithms in GraphViz (fewer crossings, faster, etc).
This is great! There are surprisingly few tools that actually output anything nice when it feels like such a doable problem.
One small improvement they could probably make is the ability to rearrange outputs at the bottom to reduce crossings. Just from the very first example it seems flipping the 0 and 1 outputs on the bottom graph would be nicer.
For anyone else interested in this general area, Steve Ruiz and Lu Wilson from tldraw often tweet a lot of fun nitty gritty edge cases in graph drawing.
34 comments
[ 3.2 ms ] story [ 43.1 ms ] threadUsually there is a good middle ground: heuristic analysis of the input to see if it fits well with special-case "stupid and fast" algorithms, and sophisticated optimizations that are the fallback and work for everything and come with guarantees.
i.e. having a general purpose diagram/graph layout is hellishly difficult, but most of the diagrams/charts follow much simpler rules, thus it's much easier to have N languages, each for 1 type of diagram, than 1 language for N types of diagrams.
I have struggled with code to diagram tools for a while [mermaid and graphviz], and usually return to figjam when I need the readabilty and aesthetics.
graph-viz is MASSIVE and a binary. mermaid requires the browser's svg rendering system to work. I just need something that builds diagrams from description easily ...
I wonder if any of these techniques turn up in whatever the magic sauce is in D2’s TALA layout engine, which is in a league of its own IMO.
https://d2lang.com/examples/tala/
Graphviz is a visualization framework and it includes many layout engines, implementing different algorithms: dot, neato, fdp, sfdp, circo, twopi, ...
It would be great if this new custom algorithm were to be contributed to Graphviz.
It used to be a that the barrier of entry of creating a new tool was high - so we had to use popular pieces of software, often stretching them, or writing plugins (that had their own constraints).
Now it is often easier to write from scratch a new piece of software, for which with have full control.
We can stand on the shoulders of giants - not just "a giant".
1. Make graphs from Clang's AST.
2. Invent some style flourish to help follow an edge that becomes part of a bundle of many edges.
Also judging from the final two images (dot vs iongraph for the same large graph) it’s clear that dot is optimized for minimal area where iongraph does not. That’s the trade off. The author claims one is more easy to navigate than the other, I think that’s debatable.
Ultimately I found that visualizing large graphs is rarely helpful in practice; they can certainly look nice for some well defined graphs, but I rarely saw well defined graphs in the wild. Ymmv but maybe some would agree?
https://github.com/eclipse-elk/elk
Dot is such a simple and readable format (particularly if using the basic features). Thus, it can make a ton of sense to define graphs in strict dot, even if you will be rendering with another tool than Graphviz.
These days, there are other popular options, too -- Mermaid, etc, as TFA indicates. Nonetheless, Graphviz/dot will remain for the long haul, IMO, because dot is so, so good.
So, you need Graphviz for its syntax definitions primarily, and because it is a standard that could be recognized/run anywhere.
[1] https://www.cs.ubc.ca/~will/536E/
[2] https://github.com/ogdf/ogdf/pulls?q=is%3Apr%20author%3Adllu...
I love how bitwig solved it: gravity, color coding, stiffness, directionality (ins on the left, outs on the right).
https://polarity.me/img/bitwig-course-02-whatisthegrid-3.jpg
One small improvement they could probably make is the ability to rearrange outputs at the bottom to reduce crossings. Just from the very first example it seems flipping the 0 and 1 outputs on the bottom graph would be nicer.
For anyone else interested in this general area, Steve Ruiz and Lu Wilson from tldraw often tweet a lot of fun nitty gritty edge cases in graph drawing.