What are the step to the Reingold-Tilford algorithm and how might I program it?

Question

From the presentation: Graphs and Trees on page 3, there is a visual presentation of what takes place during the Reigngold-Tilford process; it also gives a vague summary to this algorithm before hand: "...starts with bottom-up pass of the tree; [finishes with] Top-down pass for assignment of final positions..." I can achieve both directional passes through recursive means, and I know that the Y-value(s) are respective to each node's generation level, but I'm still lost as to how the X-coordinates are solved.

I did come across this project: A Graph Tree Drawing Control for WPF but there is so much code I had great difficulty locating what should be a simple 2-3 methods to define the X-values. (Also have no experience with WPF as well)

I have been searching and experimenting how to do this for several days now, so your help is much appreciated!

Answer 1

I found the articles listed in jwpat7's answer to be very useful, although it took me a while to figure out the exact logic needed for this algorithm, so I wrote my own blog post to simplify the explanation.

Here's the plain-text logic of how you determine the X node positions:

• Start with a post-order traversal of the tree

• Assign an initial X value to each node of 0 if it's the first in a set, or previousSibling + 1 if it's not.

  

• If a node has children, find the desired X value that would center it over its children.

  • If the node is the left-most node, set its X to that value

  • If the node is not the left-most node, set a Mod property on the node to (X - centeredX) in order to shift all children so they're centered under this node. The last traversal of the tree will use this Mod property to determine the final X value of each node.

• Determine if any of this node's children would overlap any children of siblings to the left of this node. Basically for each Y, get the largest and smallest X from the two nodes, and compare them.

  • If any collisions occur, shift the node over by however much needed. Shifting a subtree just requires adding to the X and Mod properties of the node.

  • If node was shifted, also shift any nodes between the two subtrees that were overlapping so they are equally spaced out

• Do a check to ensure that when the final X is calculated, there is no negative X values. If any are found, add the largest one to the Root Node's X and Mod properites to shift the entire tree over

• Do a second traversal of the tree using pre-order traversal and add the sum of the Mod values from each of a node's parents to it's X property

The final X values of the tree above would look like this:

I have some more details and some sample code in my blog post, but it's too long to include everything here, and I wanted to focus on the logic of the algorithm instead of code specifics.

Answer 2

A couple of articles are available that include code, in python at billmill.org and in C on page 2 of a 1 February 1991 Dr. Dobb's Journal article. You have asked for “simple 2-3 methods” (perhaps meaning cookbook methods) but drawing trees nicely in all their generality is an NP-complete problem (see Supowit, K.J. and E.M. Reingold, "The complexity of drawing trees nicely," Acta Informatica 18, 4, January 1983, 377-392, ref. 4 in the DDJ article). The Reingold–Tilford method draws binary trees more or less nicely in linear time, and Buchheim's variation draws n-ary trees more or less nicely in linear time. However, the billmill article points out (shortly after stating Principle 6), “Every time so far that we've looked at a simple algorithm in this article, we've found it inadequate...” so the likelihood of simpler methods working ok is small.