The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Need an algorithm to display a tree

I have records in a database that are related to each other in a tree fashion.  There is one root node, but after that I never know how many branches any node will have.  There could be one, there could be fifty.  I do know each time how many nodes there are total I need to draw, and I can make the assumption that it won't loop back to any previous nodes (it might, but there is code to prevent the link from being created.)  The number of nodes can and will change, but not often enough that I can't just start over whenever it changes.  I need an algorithm to consistently draw the tree to the screen.  I'm using directX, so 3D is okay and even encouraged, though not necessary.  Extra points if it's predictable (IE, if I have a fairly consistent set of nodes (likely) then each time the app is started individual nodes will be in about the same place.)  tia,
Joel
Joel Coehoorn
Thursday, July 21, 2005
 
 
It might be worth having a look at Virtual Tree View to get some ideas etc http://www.soft-gems.net
Ian H. Send private email
Thursday, July 21, 2005
 
 
Yeah, even a regular tree control would work, but that takes a very linear view of how to display the data.  Everything goes in pretty much a straight line towards the bottom.  We're going for a more balanced look that uses more of the screen.  The nodes in the database represent physical objects at a company, and the ultimate goal is to be able to include hints about the location in the record so the program will draw something close to a physical map of the nodes.
Joel Coehoorn
Thursday, July 21, 2005
 
 
If you want to get away from a linear tree, you could go to the opposite extreme within something like ThinkMap. A demo of it can be found at http://www.visualthesaurus.com
Ian H. Send private email
Thursday, July 21, 2005
 
 
Ok, that gave me some ideas for a 2D display:
1.  Draw from the center out, in ever widening perfect circles. 
2.  All connections to child nodes are made facing out from center, spread across a space = 360/# of nodes at that level.  So for the root node I have all 360 to work with.  If there are two nodes each would get 180 for it's child nodes, 4 nodes each would get 90 for it's child nodes.
3.  The distance of the connecting line is long enough to provide a minium separation (MS) from each object at the same level with node next to it.  All nodes at a level use the MS value for the node with the most sub-nodes.  There is also a minimum length for the connecting (ML).
4.  MS should be greater than ML.

I can see some problems:
1.  If a lot of the child nodes are concentrated down the same path a couple iterations in a row, than it will be very dense there and very sparse elsewhere.
2.  Under the same condition, if a bunch of nodes on other paths end, you could end up with using an angle that is too large and nodes would run into each other.

Any ideas for solutions? Speed improvements?
Joel Coehoorn
Thursday, July 21, 2005
 
 
Ok, I've been whiteboarding this and it doesn't work at all.  It assumes the spread never decreases.  I feel I'm on the right track with concentric circles, though.  Spread out all nodes at level more or less evenly along a circle (but never back towards center from the parent node).
Joel Coehoorn
Thursday, July 21, 2005
 
 
I read a paper on this one during my graduate course on how to draw trees...
Deriving Tidy Drawing of trees by Jeremy Gibbons
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#deriving

Another one I have read is
Functional pearls: Drawing trees - by Kennedy
http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf
IntentionallyLeftBlank
Thursday, July 21, 2005
 
 
Ok, this won't look as pretty, but it will be easier to implement:
Traverse the tree., counting the number of Leaf nodes (L)
Hard code the minimun distance between each leaf node (d)
Start at the top level, with nodes organized into rows.
All rows have length of L*d.
Add nodes left to right in each row.
Each node gets (number of children for this node)/(number of children for all nodes at this level) of the remaining space, and is placed at the midpoint of it's allocated space.

I think this will work, but I'm worried about it being slow, because I have to traverse before I start, and then at each row I have to know the count of children, which means an extra partial traversal.
Joel Coehoorn
Thursday, July 21, 2005
 
 
I need to add justments for nodes that have no children, but are not on the last row (I think I'll give them an imaginary child node, so they count once) and where the number nodes on the next row is 0 (so I'm not trying to divide by zero on the last row).
Joel Coehoorn
Thursday, July 21, 2005
 
 

Thursday, July 21, 2005
 
 
Take a look at TreeMaps:

http://www.cs.umd.edu/hcil/treemap/
Chris Tavares Send private email
Thursday, July 21, 2005
 
 
I've been happy with this:  http://www.treemenu.net/

Of course, what you're talking about is a pretty expensive operation, if you don't have to load it all at the same time, why not go with a Lazy Load Pattern coupled with some simple AJAX:  http://blogs.caseysoftware.com/?q=node/111
KC Send private email
Thursday, July 21, 2005
 
 
I second Graphviz. I used it to generate a company hierarchy from a database. Really easy to use. Check it out: http://www.graphviz.org/Gallery.php
Matthew Lock Send private email
Thursday, July 21, 2005
 
 
IEEE Software July/August 1990
Drawing Dynamic Trees by Sven Moen
( http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/mags/so/&toc=comp/mags/so/1990/04/s4toc.xml&DOI=10.1109/52.56447 ) [you need to buy it]

It will let you do a partial redraw when you add/remove nodes. Pretty fast, compact the drawing but it is easily controlable by the application.

You can google for it and find several implementations in C, Java and probably numerous other languages.
Val Creux Send private email
Friday, July 22, 2005
 
 
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

also has some code posted on re-balancing a tree.
KayJay Send private email
Friday, July 22, 2005
 
 
I like that treemenu in javascript. I use it for a family tree browser.
nobody
Friday, July 22, 2005
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz