Algorithm for efficiently drawing trees?

Question

I need to draw a corporate structure tree (sort-of like a family tree) in C#. All the ancillary code is there. It is colored, interactive, and fancy. The only trouble is the algorithm that actually decides where to put each node is giving me a lot of grief.

For the moment, boxes are 100x50 in size, and I have a class called StaffNode which represents a staff member at a particular x,y co-ordinate.

The algorithm just needs to create a List<StaffNode> with the appropriate x's and y's.

This is incredibly tricky.

Basically the algorithm is recursive along the corporate structure, so left->right, then top->down along the tree. Obviously it is bad if two nodes are on top of one another.

I can think of a few algorithms that might produce something like this:

          *
    o         O
o o o o o     O
o         O O O O O
                O

Whereas something like this would be better, since the tree is very large and space is very limited:

       *
    o     O
o o o o o O
o     O O O O O
            O

Have any of you had to draw a tree like this before? If you have I'm sure you've come across the many hurdles I've got. Any tips? So far I've spent an entire day on it.

Answer 1

There are many good algorithms for drawing trees, each of which shows off some different property of trees. If you want to show off a hierarchy, there is this code for WPF that draws hierarchies. For a more general discussion of how to draw graphs and trees, considering looking at these lecture slides detailing many such algorithms. There's also these excellent slides covering similar material.

Hope this helps!

Answer 2

You could use an iterative approach. Lay out the tree using something like the first example you used above. Then move nodes or subtrees closer to each other, while making sure no constraints are violated (eg: Nodes cannot overlap, child nodes must be below parent nodes).

Pros:

• Simple algorithm.
• Gets a good-enough solution.
• Can be applied continuously to a changing tree.
• Can be made to look cool.

Cons:

• May need many iterations to look good.
• May not find optimal solution (gets caught in a local maximum)