Site Map

# Thoughts and ideas about things that I find interesting

## 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!

• Hi Alex,

Spring: 16
Charge: 64
Damping: 0.9

Cheers,
Chris.

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?

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.