> I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.<p>In general, a family tree is a directed acyclic graph. Branches of the tree will always join back together if you follow the history far enough.<p>The number of ancestors in a generation is 2^N, with N being the number of generations back you're looking. There were only 100 billion people that ever lived, so by the time you get about a thousand years back, it becomes literally impossible for all your ancestors to appear only once.<p>Of course, that's just an easy upper bound to make the point that becoming a graph is unavoidable. In practice, branches will come together a lot sooner than that.
It's a source of ongoing perplexity to me that so many Linux file managers don't even offer a tree view, never mind some of the more advanced possibilities. Consider Robertson's work on Cone Trees from Xerox Parc in....1991.<p><a href="https://research.tableau.com/sites/default/files/p189-robertson.pdf" rel="nofollow">https://research.tableau.com/sites/default/files/p189-robert...</a><p>and variants thereof at <a href="https://infovis-wiki.net/wiki/Cone_Trees" rel="nofollow">https://infovis-wiki.net/wiki/Cone_Trees</a><p>Oddly, there has been some work done on <i>source code</i> trees such as Gource, but for some reason nobody has yet thought of applying this to file systems or browser navigation paths.<p><a href="https://gource.io/" rel="nofollow">https://gource.io/</a>
Was thinking was going to get some nice L-system eye candy
[0] <a href="https://en.wikipedia.org/wiki/L-system" rel="nofollow">https://en.wikipedia.org/wiki/L-system</a>
So the author mentions hearing about the Reingold-Tilford Algorithm which wouldn't work for the example given since R-T is meant for binary trees and a family tree might have more than 2 nodes.<p>Which led me to wonder why is there even an "algorithm" per se for binary trees: wouldn't it be acceptable to just trace out a complete binary tree with spaces reserved for each potential node, and only fill in a space with a node if it is non-null? Or does this not meet some criterion of "niceness" for drawings?
I'm surprised they chose that algorithm, it's fairly limited and not that efficient.<p>If your nodes have width, you should read "Improving Walker's Algorithm to Run in Linear Time" (I have an implementation here: <a href="https://github.com/Drup/tree_layout" rel="nofollow">https://github.com/Drup/tree_layout</a>)<p>If your nodes have width <i>and</i> height, you need to read "Drawing Non-layered Tidy Trees in Linear Time"<p>If you want to go bananas visualizing n-ary trees: <a href="https://treevis.net/" rel="nofollow">https://treevis.net/</a> :D
I implemented something similar at <a href="https://automations.io" rel="nofollow">https://automations.io</a> converting a workflow stored as a flat linked list to a tree structure and then traversing and rendering it out in HTML and sprinkling CSS on top
I implemented this in this app iOS:
<a href="https://apps.apple.com/us/app/collaborative-groups/id1478800849?ls=1" rel="nofollow">https://apps.apple.com/us/app/collaborative-groups/id1478800...</a>
Android: <a href="https://play.google.com/store/apps/details?id=com.groups.network" rel="nofollow">https://play.google.com/store/apps/details?id=com.groups.net...</a>
Which also has some nice features like sharing your tree with others and working together on them
Some trivial mathematical facts. No matter what algorithm you use, you want to make a quasiisometrical embedding of a tree into a finite dimensional space. Or, for a tree the no of nodes at distance R from the root is like exp R, but in any space of dimension N you can cram about R^N points which are at distance R from the origin. Hence the problem.<p>But you can embedd any tree into the Hilbert space :)
There are the various graph layout algorithms I've heard of, Sugiyama, KIELER, ELK - these can be used for trees of course, although I'm not sure they have highly constrained vertical levels like the article depicts.
Sebastian Lague did a video that includes some tree generation that was fun to watch<p>EDIT wrong kind of tree :D<p><a href="https://youtu.be/--GB9qyZJqg" rel="nofollow">https://youtu.be/--GB9qyZJqg</a>
Nice write-up. I enjoyed how the material was presented - the introduction to problem, intuitive summary method and then detailed steps with visualizations of partial results.