Graph spacing algorithm

Question

Hi, I am looking for an algorithm that would be useful for determining x y coordinates for a number objects to display on screen. Each object can be related to another object and there can be any number of relationships and there can be any number of these objects.

There is no restriction on the overall size of area on which to display these object.

I am writing this in php and would be looking to store the coordinates in an array.

Answer 1

One way to do it is to use a pseudo physics model. Your objects have a repulsive force and an attractive force if they are attached.

You move the objects according to the sum of the forces applied to them: at each step compute the sum of the forces applied to an object and move it in the force's direction.

In pseudo code, one iteration would be:

for each object o1
   force[o1] = 0
   for each object o2
      if o1 and o2 are linked
         force[o1] += attraction_force(o1, o2)
      else
         force[o1] += repulsion_force(o1, o2)

for each object o1
   move(o1, force[o1])

And stop the iterations when the objects have reached a stable state.

You will probably need to experiment with different force laws. In particular, you want to adjacent objects to reach an equilibrium quickly. I would experiment with a force intensity linear to the distance (like a spring) or quadratic (gravition/electric attraction)

Also you will probably need to move the objects randomly to prevent parts of the graph from remaining stucked. The amount of random move should be large for the first iterations and decrease with time.

Answer 2

The traditional names for what you want to do are graph layout and graph drawing. It is not in general an easy problem. The diagrams are only going to look good if they are planar or nearly planar.