Circular representation of a tree structure

Answer 1

You are trying to draw a planar representation of a graph. Find some buzzwords and perhaps a resource here And in wikipedia

Ah and I forgot: You can do this the newtonian way with forces. Simply give all nodes a repelling potential, like make them all Protons which push each other away. Give the edges the properties of newtonian springs, exerting forces that pull them together and you are all set. Could even create nice animations that way. This is also an official way of graph drawing, but I don't know the name.

Answer 2

You can do it in an emergent way by setting up a system in which each tree node tries to keep as much distance from all other nodes (except parent) as possible, but as short a distance as possible from the parent (down to some minimum distance which it must maintain). If you run that algorithm for each node repeatedly until it stabilizes, you'll have an arrangement like the one you describe. I'm sure there are a lot of optimizations you can do to it, but I'm pretty sure this is going to be the simplest approach. Trying to calculate all the layout up front would be very complex...

Answer 3

If you don't care about how it's done, but just that you are visualizing the data, then take a look at graphviz's radial layout. Although the example doesn't look exactly what you want, it is the layout you'd need. It'll also give you some ideas on how it's done too with the loads of research papers in there. Good luck!

You could also see how easy it is to extend this paper into a circular structure.

Answer 4

If you want to draw the tree with a minimum of wasted space and short connections, then you're in for a computationally expensive solution. It will be hard to get this to be realtime on a tree of decent size, not to mention that making small changes to the tree might result in a radically different equilibrium.

Another approach would be to abandon the physical simulation and just build it iteratively. I've done something similar last week, but my trees are probably a lot less involved than yours.

For this tree-layout, each node object has to store an angle and an offset. These two numbers control where on the graphics surface they end up.

Here is my basic algorithm:

1) recurse over your entire tree-data and find all the Leaf nodes. 2) while you're doing this, be sure to measure the length of each branching structure, so you know which is the longest. 3) once you have all your leaf nodes, distribute them equally over a concentric circle. You can either use the entire circle, or only some part of the angle domain. 4) once all Leaf nodes have been solved, you recurse again over the tree, going from the outside in. Each node you encounter that is not a leaf node is in need of layout. Essentially, every node from here on has an angle which is the average of all it's child nodes, and the offset is the graph_radius * (depth_of_node / maximum_depth)

I found this gives me a very decent and humanly readable distribution, albeit not a very efficient one in terms of screen usage. I uploaded an animation of my tree-display here: GIF anim