Site Map

Thoughts and ideas about things that I find interesting 

Facebook Twitter YouTube E-mail RSS
formats

Force Directed Graphs

Force directed graph algorithms are a fantastic way to calculate a very nice layout for a large network of nodes. Formerly they they were considered too expensive in terms of processing power but these days why not?

A typical force directed graph involves two forces… a charge force which causes all nodes to maintain a minimum distance apart:

(Mass of node A * Mass of node B) / Distance between the two nodes2 * -charge

… and a spring force which causes connected to attempt to maintain a given distance from each other:

(Distance between two nodes – spring) / 2.0

And of course, to prevent the nodes from moving forever it’s important to apply a damping force to their velocities.

These forces are applied to every node in the graph until the graph reaches a state of equilibrium, that is, the sum velocity of all nodes has slowed to a suitable level.

There are many different variations of force directed graph algorithms out there, and finding just the right amount of force to apply for your particular purpose is half the fun.

Last night I wrote a C# app which implements a force directed graph algorithm on a collection of interconnected OpenGL spheres and dumped the output to an AVI…

In the end, the quality of your graph will come down almost entirely to the method you use to apply the forces to your nodes.

Here’s the spring/charge algorithm in C#…

private void ApplySpringAndChargeForcesToNodes(List<Node> nodes, double spring, double charge, double damping)
{
   foreach (Node node in nodes)
   {
      foreach (Node otherNode in nodes)
      {
         if (node != otherNode)
         {
            double dx = otherNode.X – node.X;
            double dy = otherNode.Y – node.Y;
            double hypotenuse = Math.Sqrt(Math.Pow(dx, 2) + Math.Pow(dy, 2));
            double force = 0;
            if (node.IsConnectedTo(otherNode))
            {
               force = (hypotenuse – spring) / 2.0;
            }
            else
            {
               force = -((node.Mass * otherNode.Mass) / Math.Pow(hypotenuse, 2)) * charge;
            }
            dx /= hypotenuse;
            dy /= hypotenuse;
            dx *= force;
            dy *= force;
            node.DX += dx;
            node.DY += dy;
         }
      }
      node.X += node.DX;
      node.Y += node.DY;
      node.DX *= damping;
      node.DY *= damping;
   }
}

… the rest of the app was all just your usual form control and OpenGL lighting and blending stuff.
There’s a lot of satisfaction in seeing your graph reach equilibrium for the first time, so if you’re planning on incorporating a force directed graph algorithm into whatever you happen to be working on I wish you the best of luck!

12 Responses

  1. Alex

    Nice article. Do you have any more info on what spring, charge, and dampening values/calculations to use?

    Thanks!

  2. Erik

    Hi Chris,

    Can you let us know, the Node structure and the use of DX and DY is Node class…? And if you have saved the nodes in tree structure (parent node is holding its connected child nodes) then why there is a need of IsConnectedTo check…

    Thanks,
    Erik

    • Chris

      Hi Eric,

      dx and dy are just the difference between one nodes xy and another’s.

      As it turns out, the graph in the example could have been represented in a tree structure, but because a network can’t be represented as a tree each node needs a record of the other nodes they’re attached to. (That’s why there’s the IsConnectedTo check)

      Cheers,
      Chris.

  3. Jolan

    Hi Chris,

    firstly, thank you for this.

    I would like to know about the mass of nodes, and the “normal” value of dx and dy.

    Thanks,
    Jolan

  4. Shahid

    Good one. You have to play around with the parameters a bit but its a very elegant start. A few things I found useful:

    - Anchor some node to the center, so that the constellation doesn’t fly off
    - Your spring parameter sould be some percentage of the screen resolution e.g. with 10 nodes and 1920×1080, i was using 300 as the spring param i.e. expected length of edges

    An interesting extension could be where the algorithm can learn the optimal spring, charge and damping parameters, i.e. given window dimensions, and desired time of convergence, current frame rate, and number of nodes, …

  5. tomas

    hi, i want to ask, where you get node.x and node.y values?
    for example, in my program, i am parsing pajek, to adjacency matrix.
    But from pajek i cant get x a y positions, so how you get x and y at the begining?
    thank for answer

  6. Måns

    Thanks a bunch, short and sweet!

  7. Raphael

    Hi,
    Thank you for this great article and video!
    I’m a beginner to openGL and it’s pretty hard for me to imagine how you draw these edge and node in openGL.
    Would you mind open the source code of your C# app?
    Thanks you

    • Chris

      Hi Raphael, it’s been a while and I probably don’t have it any more. I know I used the Tao OpenGl .Net library though. I hope that helps!

  8. Ricardo Cruz

    With what values do you initialize node.DX and node.DY?

    • Chris

      Hi Ricardo,

      Something small and random… Between 0.1 and 0.5. The faster the nodes are traveling to begin with the longer the graph will take to settle so keep the initial velocity small.

      Cheers,
      Chris.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>