Hello all, I've been stuck on this problem for about two weeks now, and have tried various things to make it work, but none of them are ideal... How can I present a tree, where each node can have multiple inputs and outputs, visually to a user, such that any given node will have a unique position in 2D space and never overlap another node? The logic for the tree is implemented and works fine, but I want to be able to display this to the user to give visual feedback on how nodes are linked. I can already determine the 2D size of node (a box is fine), and this size can be used for all nodes, so that should make rendering of the tree easier. I've tried using a bounding box to ensure nodes don't overlap, but this introduces problems when trying to place children nodes. For example (warning: ASCII art follows, the '*' marks denote the bounding box vertices):

*       *
 +-+
 |A|
 +-+
  |
 +-+ +-+
 |B|-|C|
 +-+ +-+
*       *

Then if I add a child to B, this works fine:

*       *
 +-+
 |A|
 +-+
  |
 +-+ +-+
 |B|-|C|
 +-+ +-+
  |
 +-+
 |D|
 +-+
*       *

But when I add another child to B, it shifts E too far to the right because of the bounding box (ideally it would be positioned next to D, assuming D didn't have any siblings):

*           *
 +-+
 |A|
 +-+
  |
 +-+ +-+
 |B|-|C|
 +-+ +-+
  | \___
 +-+    \+-+
 |D|     |E|
 +-+     +-+
*           *

So I'm guessing a bounding box isn't the proper way to do this. :( I've tried searching Google, but I'm not really sure what to search for, seeing as how "rendering a tree" turns up nothing of what I'm interested in. Are there any algorithms which describe how to do something like this? Any help would be greatly appreciated!

Sounds like some kind of constraint based placement problem...

Here is an example of an interactive applet - you'll obviously want something a little more involved.

HTH

As long as it's a tree and not a graph, you can display it in the same format used by directory trees. That is, each level has a horizontal position and children appear below their parent.

-main
--child1
---childa_of_child1
---childb_of_child1
--child2
---childa_of_child2

and so on...

Does Graphviz do what you want? If so, the easiest approach is to generate a .dot file (which just defines the nodes and edges in a text-based format) and then run Graphviz to generate the image for you, since they've already done the hard work.

ajones: Thanks! That's a rough idea of what I need, so I'll start to research it a bit.

kvp: Sorry, I probably shouldn't have used the word "tree", because it can't be visually described like that. Each node can have multiple inputs (parents) and multiple outputs (children), as well as siblings. However, the nodes are guaranteed to not be recursive upon each other. So a simple tree-view won't cut it here.

Excors: Yes! Now that's more of what I was looking for. The first image on left in the header at the top of the page is perfect. Unfortunately (for me), my application is written in Flash ActionScript, so I'll have to poke through Graphviz's source code for dot and see how they do it...

Thanks for the suggestions! I'm still open to any other ideas should anyone else have any. :)

This sounds suspiciously like this project, which I am working on. ;)