6 ms·

Algorithm for Drawing Trees

189 points by mfbx9da4 7y ago

virtuous_signal 7y ago
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. 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?
- captncraig 7y ago
  If you do that, you quickly run into the feasible depth limit for what you can show in a fixed space. Especially for sparse trees. Consider something like family trees, where you generally don't know anything about certain lines, but may have 20 generations or more on selected lines. No way could you show 2^20 nodes in a fixed format rendering, but you can make something kinda pretty by eliminating the empty space and organizing things to fill it intelligently.
  - taywrobel 7y ago
    I was just writing a radial RT-like visualization for displaying the branching structure of a binary tree and ran into the issue of information density you describe. Still pretty happy with the results, tho, in how it shows the structure and clustering. And I colored it like a tree, just for fun - https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5 https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5
- raegis 7y ago
  That only works for complete (or "nearly" complete) binary trees, and you can't draw many of these since the number of children in a generation grows exponentially. For most trees you have to try to keep the width minimal while avoiding collisions between deeply-nested left and right children. One of the earlier papers to give some precise "niceness" criteria is "Tidier Drawings of Trees" (https://reingold.co/tidier-drawings.pdf https://reingold.co/tidier-drawings.pdf) by Reingold and Tilford, with a companion Pascal program for computing the coordinates.
  - virtuous_signal 7y ago
    Fantastic. I would not have thought that binary-tree-drawing could be such a complicated problem.
    - ygra 7y ago
      Graph drawing in general is a field full of complicated problems.
tunesmith 7y ago
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.
- ygra 7y ago
  Sugiyama has layers and can be used for trees just as well (and may give nicer results for almost-trees than removing non-tree edges and routing them individually). KIELER and ELK seem to be collections of various layout algorithms, including Sugiyama and specialized tree layout algorithms (same with our own library yFiles).
winrid 7y ago
Sebastian Lague did a video that includes some tree generation that was fun to watch EDIT wrong kind of tree :D https://youtu.be/--GB9qyZJqg https://youtu.be/--GB9qyZJqg
sprt 7y ago
This is interesting, I was asked this question in an interview for a Microsoft internship, but for a binary tree.
tejtm 7y ago
Was thinking was going to get some nice L-system eye candy [0] https://en.wikipedia.org/wiki/L-system https://en.wikipedia.org/wiki/L-system
michaeltoth 7y ago
I was expecting a generative art algorithm for drawing trees
javieranton 7y ago
I implemented this in this app iOS: https://apps.apple.com/us/app/collaborative-groups/id1478800849?ls=1 https://apps.apple.com/us/app/collaborative-groups/id1478800... Android: https://play.google.com/store/apps/details?id=com.groups.network https://play.google.com/store/apps/details?id=com.groups.net... Which also has some nice features like sharing your tree with others and working together on them
anigbrowl 7y ago
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. https://research.tableau.com/sites/default/files/p189-robertson.pdf https://research.tableau.com/sites/default/files/p189-robert... and variants thereof at https://infovis-wiki.net/wiki/Cone_Trees https://infovis-wiki.net/wiki/Cone_Trees Oddly, there has been some work done on source code trees such as Gource, but for some reason nobody has yet thought of applying this to file systems or browser navigation paths. https://gource.io/ https://gource.io/
- j88439h84 7y ago
  There's https://dystroy.org/broot/ https://dystroy.org/broot/ Are those fancy tree displays actually useful for anything or is just pretty?
  - ShamelessC 7y ago
    Yeah I think it's obvious that graphical trees are prettier than they are effective user interfaces. Broot is a good example of just how much effort goes into making nested structures easily navigable. Trees may be good for presentation but ultimately lists with indentation for nesting are for more navigable. This translates to GUI concepts as well. Both Windows and MacOS show a few flat lists relative to the current directory rather than showing all nestings at once like a tree does.
  - anigbrowl 7y ago
    That's for console use. Trees are useful for looking at the whole thing at once, much as it's easier to appreciate a real tree that way than by maintaining a list of the leaves and branching distances. I'm a a researcher and my source material is ~50gb spread across ~50k hand-picked files with pretty arbitrary structure, plus another 4-5 times that in mirrors of other collections. Trees let me see things that I would overlook by reading lists all the time. Right now I half-ass use some bioinformatics tools originally intended for cladistics and proteome research to visualize the collection. Some days I go looking for specific information or catalog what I have, other days I stumble across a cache of valuable data and might select hundreds of individual files.
HatchedLake721 7y ago
I implemented something similar at https://automations.io https://automations.io 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
slavik81 7y ago
> I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree. 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. 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. 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.
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]
- erdeszt 7y ago
  Is it always acyclic though? https://stackoverflow.com/questions/6163683/cycles-in-family-tree-software https://stackoverflow.com/questions/6163683/cycles-in-family...
  - slavik81 7y ago
    Yes. You cannot be your own ancestor. A graph pointing from child to parent can split and merge, but never loop. Though, you may need a cyclic directed graph for fictional family trees and time travel paradoxes.
    - tgv 7y ago
      And data entry errors...
    - rhn_mk1 7y ago
      A family tree is an overloaded term. The tree of ancestry, which describes who beget whom, sure cannot be cyclical. The graph of civil relationships can certainly contain cycles. If the relationship in question is "is a legal parent of", for example, then adopt your parent. The opportunities for cycles multiply if both blood and legal relationships are taken into account.
jmiskovic 7y ago
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.
Drup 7y ago
I'm surprised they chose that algorithm, it's fairly limited and not that efficient. If your nodes have width, you should read "Improving Walker's Algorithm to Run in Linear Time" (I have an implementation here: https://github.com/Drup/tree_layout https://github.com/Drup/tree_layout) If your nodes have width and height, you need to read "Drawing Non-layered Tidy Trees in Linear Time" If you want to go bananas visualizing n-ary trees: https://treevis.net/ https://treevis.net/ :D
xorand 7y ago
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. But you can embedd any tree into the Hilbert space :)
billfruit 7y ago
I remember Robert Sedgewick's listed a really simple method for drawing trees in his book, only it drew them sideways.

189 points by mfbx9da4 7y ago

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. 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?

captncraig 7y ago
If you do that, you quickly run into the feasible depth limit for what you can show in a fixed space. Especially for sparse trees. Consider something like family trees, where you generally don't know anything about certain lines, but may have 20 generations or more on selected lines. No way could you show 2^20 nodes in a fixed format rendering, but you can make something kinda pretty by eliminating the empty space and organizing things to fill it intelligently.
- taywrobel 7y ago
  I was just writing a radial RT-like visualization for displaying the branching structure of a binary tree and ran into the issue of information density you describe. Still pretty happy with the results, tho, in how it shows the structure and clustering. And I colored it like a tree, just for fun - https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5 https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5
raegis 7y ago
That only works for complete (or "nearly" complete) binary trees, and you can't draw many of these since the number of children in a generation grows exponentially. For most trees you have to try to keep the width minimal while avoiding collisions between deeply-nested left and right children. One of the earlier papers to give some precise "niceness" criteria is "Tidier Drawings of Trees" (https://reingold.co/tidier-drawings.pdf https://reingold.co/tidier-drawings.pdf) by Reingold and Tilford, with a companion Pascal program for computing the coordinates.
- virtuous_signal 7y ago
  Fantastic. I would not have thought that binary-tree-drawing could be such a complicated problem.
  - ygra 7y ago
    Graph drawing in general is a field full of complicated problems.

tunesmith 7y ago

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.

ygra 7y ago
Sugiyama has layers and can be used for trees just as well (and may give nicer results for almost-trees than removing non-tree edges and routing them individually). KIELER and ELK seem to be collections of various layout algorithms, including Sugiyama and specialized tree layout algorithms (same with our own library yFiles).

winrid 7y ago

Sebastian Lague did a video that includes some tree generation that was fun to watch EDIT wrong kind of tree :D https://youtu.be/--GB9qyZJqg https://youtu.be/--GB9qyZJqg

sprt 7y ago

This is interesting, I was asked this question in an interview for a Microsoft internship, but for a binary tree.

tejtm 7y ago

Was thinking was going to get some nice L-system eye candy [0] https://en.wikipedia.org/wiki/L-system https://en.wikipedia.org/wiki/L-system

michaeltoth 7y ago

I was expecting a generative art algorithm for drawing trees

javieranton 7y ago

I implemented this in this app iOS: https://apps.apple.com/us/app/collaborative-groups/id1478800849?ls=1 https://apps.apple.com/us/app/collaborative-groups/id1478800... Android: https://play.google.com/store/apps/details?id=com.groups.network https://play.google.com/store/apps/details?id=com.groups.net... Which also has some nice features like sharing your tree with others and working together on them

anigbrowl 7y ago

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. https://research.tableau.com/sites/default/files/p189-robertson.pdf https://research.tableau.com/sites/default/files/p189-robert... and variants thereof at https://infovis-wiki.net/wiki/Cone_Trees https://infovis-wiki.net/wiki/Cone_Trees Oddly, there has been some work done on source code trees such as Gource, but for some reason nobody has yet thought of applying this to file systems or browser navigation paths. https://gource.io/ https://gource.io/

j88439h84 7y ago
There's https://dystroy.org/broot/ https://dystroy.org/broot/ Are those fancy tree displays actually useful for anything or is just pretty?
- ShamelessC 7y ago
  Yeah I think it's obvious that graphical trees are prettier than they are effective user interfaces. Broot is a good example of just how much effort goes into making nested structures easily navigable. Trees may be good for presentation but ultimately lists with indentation for nesting are for more navigable. This translates to GUI concepts as well. Both Windows and MacOS show a few flat lists relative to the current directory rather than showing all nestings at once like a tree does.
- anigbrowl 7y ago
  That's for console use. Trees are useful for looking at the whole thing at once, much as it's easier to appreciate a real tree that way than by maintaining a list of the leaves and branching distances. I'm a a researcher and my source material is ~50gb spread across ~50k hand-picked files with pretty arbitrary structure, plus another 4-5 times that in mirrors of other collections. Trees let me see things that I would overlook by reading lists all the time. Right now I half-ass use some bioinformatics tools originally intended for cladistics and proteome research to visualize the collection. Some days I go looking for specific information or catalog what I have, other days I stumble across a cache of valuable data and might select hundreds of individual files.

HatchedLake721 7y ago

I implemented something similar at https://automations.io https://automations.io 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

slavik81 7y ago

> I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree. 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. 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. 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.

deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
erdeszt 7y ago
Is it always acyclic though? https://stackoverflow.com/questions/6163683/cycles-in-family-tree-software https://stackoverflow.com/questions/6163683/cycles-in-family...
- slavik81 7y ago
  Yes. You cannot be your own ancestor. A graph pointing from child to parent can split and merge, but never loop. Though, you may need a cyclic directed graph for fictional family trees and time travel paradoxes.
  - tgv 7y ago
    And data entry errors...
  - rhn_mk1 7y ago
    A family tree is an overloaded term. The tree of ancestry, which describes who beget whom, sure cannot be cyclical. The graph of civil relationships can certainly contain cycles. If the relationship in question is "is a legal parent of", for example, then adopt your parent. The opportunities for cycles multiply if both blood and legal relationships are taken into account.

jmiskovic 7y ago

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.

Drup 7y ago

I'm surprised they chose that algorithm, it's fairly limited and not that efficient. If your nodes have width, you should read "Improving Walker's Algorithm to Run in Linear Time" (I have an implementation here: https://github.com/Drup/tree_layout https://github.com/Drup/tree_layout) If your nodes have width and height, you need to read "Drawing Non-layered Tidy Trees in Linear Time" If you want to go bananas visualizing n-ary trees: https://treevis.net/ https://treevis.net/ :D

xorand 7y ago

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. But you can embedd any tree into the Hilbert space :)

billfruit 7y ago

I remember Robert Sedgewick's listed a really simple method for drawing trees in his book, only it drew them sideways.