Force-Directed graph layout approximation part I

I've been working on these last days in a Force-Directed graph layout approximation applicated in my VLO Framework (That's why I've been off these days without posting anything). The system consists on applying physics laws to each node calculating the repulsion force using Coulomb's law and the attractive force using Hooke's law. To do this, I've made a lot of changes to accomplish all the requirements of the new functionality. Now, every TBox class implements a TNode class which has all the physics components like hooke_force, coulomb_force, speed, mass, etc. And the manager ThundaxBoxManager that handle all the canvas methods now implements the TGraph class which has all the data about repulsion calculation, attraction calculation, the energy of the system, etc. The algorithm is easy to understand because it works in a simple way. We need to iterate every node and calculate in steps the hooke and Coulomb force for everyone. In every step, there will be new forces that interact with each node, and when the total amount of energy is nearly zero, we can stop the algorithm.

I've been searching on the internet different approximations in many programming languages, but I've only found it in Javascript, Perl and python. My approximation is done with Delphi, and I've made a win32 desktop application to show you this:

• TestFramework v2.0.0 build 470 (with data)

You only need to run the program, create the different nodes, connect them with edges and then play the force-directed layout algorithm. I'm still refactoring some parts of the code and I think I'll release another build in a few days.

I've also made some videos that show the running of the algorithm:

In these videos, you can see different representations of graphs and it's new representation after applying the force-directed layout. With this algorithm, we make the graph more human-readable and understandable. If we take a look at the second video, this shows you that if we put more than one graph, the system is capable to show you all of them separately applying physic's laws.

• The algorithm:

The algorithm consists of the calculation of the different forces that every node as a particle has and continue with this until a level of kinetic energy is reached. The skeleton of the algorithm looks like this:

while (not calculation_finished)
total_kinetic_energy := 0
for i := 0 to Boxlist.Count - 1 do
begin
    node := Boxlist.items[i];
    node.CoulombForce.setVal(0, 0);

    for j := 0 to Boxlist.Count - 1 do
    begin
        other_node := Boxlist.items[j];
        node.CoulombForce := node.CoulombForce + Coulomb_repulsion( node, other_node )
    end;

    for k := 0 to Boxlist.Count - 1 do
    begin
        node := Boxlist.items[i];
        node.hookeForce.setVal(0, 0);
        for l := 0 to High(node.Neighbour) do
        begin
          other_node := node.Neighbour[l];
          node.hookeForce := node.hookeForce + Hooke_attraction( node, other_node )
        end;
    end;

    node.speed.x := node.speed.x + (node.CoulombForce.X + node.hookeForce.X));
    node.speed.y := node.speed.y + (node.CoulombForce.Y + node.hookeForce.Y));

    total_kinetic_energy := total_kinetic_energy + node.mass * sqr(node.velocity);
end;

if total_kinetic_energy < Epsilon then
   calculation_finished := true;
end;

In this piece of code (I'll describe this better in the next articles) we can see the easy calculation of the system. We only need to add some properties to the classes and calculate correctly the different forces (here is the big problem).

For the next days, I'm preparing different articles showing this interesting approximation going through the different classes, and news features that I've had to build to improve the performance of the GUI. I hope you find interesting this and don't hesitate to leave any comment on the post.