Algorithm for Drawing Trees

I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.

At the time, I thought “This will be easy, I’ll just Google for an algorithm to determine the X,Y position of each node, then do something to draw each node on the screen”.

But it turns out Googling for a simple and easy-to-follow algorithm for drawing nice trees is very hard.

My initial Google attempts lead me to the Reingold-Tilford Algorithm.

more….

there was some fella Donald something or another used to write about things like this, very difficult to understand it was too

Tau.Neutrino said:

Algorithm for Drawing Trees

I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.

At the time, I thought “This will be easy, I’ll just Google for an algorithm to determine the X,Y position of each node, then do something to draw each node on the screen”.

But it turns out Googling for a simple and easy-to-follow algorithm for drawing nice trees is very hard.

My initial Google attempts lead me to the Reingold-Tilford Algorithm.

more….

I can do ferns:

https://newtonexcelbach.com/2010/10/03/faster-ferns/

Tau.Neutrino said:

Algorithm for Drawing Trees

I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.

At the time, I thought “This will be easy, I’ll just Google for an algorithm to determine the X,Y position of each node, then do something to draw each node on the screen”.

But it turns out Googling for a simple and easy-to-follow algorithm for drawing nice trees is very hard.

My initial Google attempts lead me to the Reingold-Tilford Algorithm.

more….

Plenty of algorithms for drawing family trees. Every piece of family tree software has one. I use Brothers Keeper, but its method for drawing trees is not good so I use collapsed descendants list instead. Essentially it turns the tree into a list with one (or two or 3) lines for each node.

The trees I’m used to are binary trees, and to a lesser extent family trees and K-D trees. There’s a tree-drawing algorithm in “the blind watchmaker” but you don’t want that because it allows branches to overlap. There’s also a tree-drawing capability within wikipedia that I’ve used, but I don’t recommend it. I haven’t heard of the Reingold-Tilford Algorithm but the output looks good, both in its x-y form and in its circular form.

“Tidier Drawings of Trees” by E.M. Reingold ; J.S. Tilford IEEE Transactions on Software Engineering (Volume: SE-7 , Issue: 2 , March 1981) Page(s): 223 – 228
https://www.reingold.co/tidier-drawings.pdf

> We have implemented Algorithm TR in Pascal; the bulk of the work is done by the recursive postorder traversal procedure shown in Fig.6.

If you have the patience, the algorithm from the paper can be simply cut and pasted from the paper (Figure 6 and 8) into a text file, then cleaned up.

I once learnt Pascal, and the program looks easily translatable into any old computer language such as Fortran, C or Basic.

Have you had a look at this yet? https://en.wikipedia.org/wiki/List_of_phylogenetic_tree_visualization_software

mollwollfumble said:

Tau.Neutrino said:

Algorithm for Drawing Trees

I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.

At the time, I thought “This will be easy, I’ll just Google for an algorithm to determine the X,Y position of each node, then do something to draw each node on the screen”.

But it turns out Googling for a simple and easy-to-follow algorithm for drawing nice trees is very hard.

My initial Google attempts lead me to the Reingold-Tilford Algorithm.

more….

Plenty of algorithms for drawing family trees. Every piece of family tree software has one. I use Brothers Keeper, but its method for drawing trees is not good so I use collapsed descendants list instead. Essentially it turns the tree into a list with one (or two or 3) lines for each node.

The trees I’m used to are binary trees, and to a lesser extent family trees and K-D trees. There’s a tree-drawing algorithm in “the blind watchmaker” but you don’t want that because it allows branches to overlap. There’s also a tree-drawing capability within wikipedia that I’ve used, but I don’t recommend it. I haven’t heard of the Reingold-Tilford Algorithm but the output looks good, both in its x-y form and in its circular form.

“Tidier Drawings of Trees” by E.M. Reingold ; J.S. Tilford IEEE Transactions on Software Engineering (Volume: SE-7 , Issue: 2 , March 1981) Page(s): 223 – 228
https://www.reingold.co/tidier-drawings.pdf

> We have implemented Algorithm TR in Pascal; the bulk of the work is done by the recursive postorder traversal procedure shown in Fig.6.

If you have the patience, the algorithm from the paper can be simply cut and pasted from the paper (Figure 6 and 8) into a text file, then cleaned up.

I once learnt Pascal, and the program looks easily translatable into any old computer language such as Fortran, C or Basic.

Have you had a look at this yet? https://en.wikipedia.org/wiki/List_of_phylogenetic_tree_visualization_software

So, anyone want to take this further? By for instance finding a good tree drawing program in C, VB or Java?

Or develop their own algorithm for instance from one level of branches to the next by offsetting each node for the new level equally from the old level, then expanding the old level when there’s a conflict of position in the new level?