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;
force = (hypotenuse – spring) / 2.0;
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!