Graph theory - force based autolayout algorithm

Question

Just want to check I have my theory right before I start implementing.

Constants:

• m = mass of vertex (all the same - probably set this to radius of node)
• k = constant edge force.
• l = length of edge at "energy minimal state".

Variables:

• d = distance between two vertices.
• cl = current length of edge.

Theory: Every vertex has a repulsion force on every other vertex which is: m / (d^2). For every edge it exhibits a force both vertices "dragging" them in the direction to get the edge to the "energy minimal state"; so each vertex: -k * ((l - cl) / 2).

Pseudocode:

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

Comments: So would this work? What should I set m and k to?

Answer 1

You're on the right lines. Your terminology/physics is a bit off: what you're calling mass and "k" is sort of all mixed up with what would better be called "charge" (for the inverse-square law repulsion) and "spring constant" for the Hooke's Law attraction.

As noted in comment replies to your question, you do need some damping which actually takes energy out of the system, else it will just oscillate converting potential energy to kinetic energy and back forever. Worse, simulation accuracy issues can easily lead to energy increasing indefinitely and the simulation "going crazy" if you're not careful.

This wikipedia article has some nice pseudocode which you'll find very similar to yours, but with the above points addressed (although note that even that pseudocode is missing a divide-by-mass in the acceleration calculation; see the page's discussion).

You also need to think a bit about the initial distribution you'll start the simulation from, and how you much you care about the possibility of getting stuck in a local minimum if a (perhaps) much better global minimum exists. These points are related; a lot depends on the topology of your graph. If it's a simple tree you'll have little trouble getting a nice layout. If it's got lots of loops and structure... good luck.

Answer 2

I would not choose the same m for each vertex. Instead, I would make it proportional to the number of other vertices it is connected to. That way, extremities of the graph who fly away to their position faster away than highly connected ones.

I have no idea for k.