High-performance tidy trees visualization (2022) | Hacker News Reader

High-performance tidy trees visualization (2022)

zxch3n.com

231 pointsczx11133121 comments

This is great.

It's beautiful, and you've explained the field of tidy tree generation really well.

I wish I had this to refer to last year when implementing something similar in VBA for Excel and PowerPoint [1]. Perhaps it's time for me to revisit!

[1] https://aaronbrooker.com/vdttool

Beautiful and impressively fast! I wonder if this could be adapted to work with [1] “dot” graphs through the terminal?

[1] https://graphviz.org/doc/info/command.html

I'd love that! For my CRDT work, I stare at a lot of graphs to figure out bugs and optimize.

For example, here's the causal graph of changes made to git's Makefile:

https://josephg.com/git-makefile.dt.svg

Having a nicer way to render these graphs (and especially show them in the browser) would be delightful!

At work I also used to stare at a lot of graphs to figure out bugs. We reuse some of the graphs so we've gone through the effort of recording node positions in metadata and given the graphs a UI where people can drag nodes around and re-save. But it's clunky.

I always wished I could invent some domain-specific heuristics to lay out the graph automatically but never took the time to.

Manually moving nodes actually worked fairly well for our use case, but it made a mess of text diffs when e.g. nodes were inserted and the position of all subsequent nodes shifted, so as a consequence we had to invent ways to visually diff graphs. Maybe the improved automatic layout would have been easier after all.

Yes, I use a similar approach when debugging some parts of my CRDTs as well. It's very helpful.

However, this algorithm is designed specifically for trees. I'm not sure whether I could manage to make it work on DAGs (Directed Acyclic Graphs). It would require some rewrites of the aesthetic rules and designing a new algorithm.

The way we do it at work is to have a separate step before a tree layout that removes non-tree edges, lays out the tree, and then re-insert the edges and calculates separate routes for them. You can play with this here by adding new edges and re-layouting: https://live.yworks.com/demos/layout/layoutstyles/index.html...

That being said, those edges of course sometimes just won't fit nicely into the general layout. And which edges are "tree" edges and which are "non-tree" edges can of course be debatable. If a graph is very much not a tree, this can be somewhat random, but it works very well for graphs that are mostly trees.

Thanks for sharing. I might be able to build upon this.

I would choose Plotly or D3 subset of DAGs or something even like Meanim (3blue1brown) where you can have a proper depth dimension.

Probably not. This algorithm is specifically designed for trees, not graphs.

But trees are a subset of graphs, so it’s probably is possible, right?

Nice work.

@czx111331 - based on your new algo, how much cognitive improvement do you think would be possible on website trees like this one: https://app.visualsitemaps.com/share/5649338316a9b89f00ef617...

here's the Json: https://gist.github.com/visualsitemaps/94f88f1ffadea91204eb2...

Probably little. Because the tree is flat and wide, different tree layout algorithms have little effect on the overall compactness. However, I guess it might be improved by using an outline view like Workflowy.

is that some kind of lib/algo? or are you referring to this? https://workflowy.com/

Yeah, I'm referring to this. In essence, it's like a mind map that expands from left to right in a compact format. There are similar things like Logseq and Roam Research. Although the view is designed mostly for text, I think it is useful for visualizing flat and shallow trees. Though it might look less fancy, it's readable on mobile, and can display the hierarchy more clearly without disturbing lines, which contribute little information when reading.

Does everyone else feel like optimal/efficient algorithms are _significantly_ easier to intuit once you know the achievable complexity? My initial guess was that this algorithm would be n log n, but once I read that the solution space was linear, I instantly came up with some linear approaches.

It's quite common during competitive programming (algorithms and datastructure). In many of the of contests your given input size constraints and time limit. Knowing that helps you narrow down which approaches or tools you shouldn't even try because they would be too slow, or when to stop because you came up with something good enough.

In few contests that don't give precise input limits, it adds extra challenge. And if your idea for the optimal efficiency is wrong, you have not only wasted time implementing wrong solution, but might also get a penalty score for each failed submission. One of the worst feelings is when you see that your submission got time limit on something like test 87, and you are unsure whether it's due to having wrong asymptotic complexity or whether you have correct algorithm but just implemented it slightly too inefficiently and it only needs a little bit of minor optimizations to pass.

Yes, maybe, since you can start working from the little pieces up to the big pieces, rather than the other way round. When you first see it, there could be all kinds of potential loci of interest being thrown at your face: the individual nodes, the neighbors of the nodes, the branching, the directionality, the depth of the thing, etc. so it takes you striking down the details you pick to not think about . So you start off with the biggest description of the possible solution space, unless you are trained seriously enough to just ‘see the answer’ without blinking to that first question of what to focus on. But if you get the complexity before hand, well that indexes quite swiftly into the potential domain spaces.

This should be a pattern for how to explain CS things online

1010

very helpful

Reply on news.ycombinator.com