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)
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?
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).
[1] https://www.cs.ubc.ca/~will/536E/
[2] https://github.com/ogdf/ogdf/pulls?q=is%3Apr%20author%3Adllu...
This is a great write up.
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.
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.
anyone working on this space easily gets a +1!
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 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.
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.
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.
this article is confusing, it appears to conflate graphviz (an umbrella term/tool that collects a set of layout engines and output formats) with both dot (a specific layout engine) and sstangl/iongraph (a specific tool that transforms a particular SSA/AST input format to a specific dot output format)
it also seems to conflate how a DAG is expressed, with how that expression is rendered
strange
I feel like going to the source of an algorithm/implementation is a super power, as illustrated by this example.
Having used Graphviz for fairly complex visualizations I was initially shocked that someone would rewrite it themselves. Then I saw the breakdown of the algorithm and realized it may not be as complicated as I first thought.
All that being said, as a general rule it is hard to know what the hidden complexities may be until you are finished implementing the algorithm.
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.
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?
Wow, thank you very much. I like the graphviz dot language. I may translate this to Rust.
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.
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.
looking at the spagetti: neither is readable, but I'd say wonky graphviz wins because you have a chance following some of the lines.
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
Wonder how it compares with elkjs? I had written a few things that wrapped dot, which felt clunky, but have since had good success writing react components that use elkjs. Elkjs has a stupid amount of configuration options, some of which aren't very clearly documented, but I've been able to get decent output for use cases like argument mapping and choose-your-own-adventure maps.
Looks nice. Two things on my wish list:
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.
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.
One of the nice things about this work is that by assuming the environment is a web client, it supports some basic interactive exploration, and offloads a lot of bothersome rendering problems.
Also, by focusing on control flow graphs, the proposed method does a better job with domain-specific layout. Apparently CFG visualization and exploration is a current topic; e.g. CFGExplorer. Probably Graphviz some users would benefit if it incorporated CFG-friendly level assignment as an option.
There's already machinery in Graphviz to support polylines instead of splines, and to control edge ordering, but it is not well tested or documented. It seems tempting to incorporate an edge routing algorithm of Brandes and Kopf, based on long vertical runs with at most 2 bends per edge. This seems close to a master's degree worth of work to understand and implement.
Graphviz started almost 40 years ago, is only supported by a few (one or two?) 2nd-generation volunteers with no 3rd generation on the scene yet. Over the years we've had plenty of our own disdainful "What is all this junk" moments, about our own code and other people's (c.f. various xkcd comics), but sometimes a better perspective is asking "What is being optimized that led to some team choosing or ending up at this point in the design space". Generally, the market is addicted to features.
It is a little dismaying to see the relatively slow progress in the broad field of declarative 2d diagramming. Given the way the pendulum has swung so hard back toward language based methods and away from using interaction to do everything, you'd think there would be a bigger payoff now for doing the work. Unfortuantely tool-making has always been a tough market. The customers are generally smart, demanding, and work in cost centers so don't have generous budgets.
This is a very nicely presented graph layout algorithm, and it produces very readable CFG output.
eclipse also does better than dot, but it's useful to notice that graphviz never dies
Interesting. How do you get the examples to run?
please make this as agent for AI
[dead]
[dead]
[flagged]
I added one statement and it only says `timed out`. I'll stick with Graphviz, which certainly doesn't time out.
It is one of the game changers of AI.
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".
To be more accurate, the comparison is not with Graphviz, but with dot(1).
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.