Force-based graph drawing in AS3
This post will be dedicated to drawing graphs in an aesthetically pleasing way. We will use physics “spring” algorithm, and create real-time simulation.
Updates
- you can check out my My tool for drawing graphs in JavaScript!
- there is a 3D version of the flsah graph drawer!
Graphs and their drawing
Graphs
A graph is defined by a set of vertices (e. g. ${a, b, c, d}$) and a set of edges, which are the pairs of vertices ($\{ \{ a,b\}, \{b,c\}, \{c,d\}, \{d,a\}\}$). Most of people would draw this graph as a “square”, but there are many ways to draw it. Some of them are “nicer” than others.What is “nicely” drawn graph
Let’s try to define it. At first, we don’t want vertices to be too close to each other. Edges should have more or less equal length and don’t cross each other too often. We can define a lot of criterias.Spring model
In this model, we add an “antigravity” to each node. Due this, edges won’t be too close to each other. We add a spring (an attraction power) between vertices, where is an edge between them. After few iterations (re-counting the power values and re-moving vertices to new positions) we will have a nice looking graph.I just implemented the algorithm described in this article on Wikipedia.
Vertex class
package
{
import flash.display.Sprite;
import flash.geom.Point;
public class Vertex extends Sprite
{
// speed of vertex
public var velocity:Point = new Point();
// force twards other vertices in the network
public var net_force:Point = new Point();
public var isDragged:Boolean = false; // I can drag the vertex
public function Vertex():void
{
// I draw a ring into the middle
with(graphics)
{
beginFill(0xFF005E);
drawEllipse(-12, -12, 24, 24);
endFill();
}
}
}
}
Creating a graph
// set of vertices
vertices = new Vector.< Vertex >(n, true);
// set of edges in symetric incidence matrix
edges = new Vector. < Vector.< Boolean >>(n, true);
for(i=0; i < n; i++) edges[i] = new Vector.< Boolean >(n, true);
while(e > 0) // add some edges
{
var a:int = Math.floor(Math.random()*n);
var b:int = Math.floor(Math.random()*n);
if(a==b || edges[a][b])continue;
edges[a][b] = true;
edges[b][a] = true;
e--;
}
// creating vertices
for(i=0; i < n; i++)
{
var v:Vertex = new Vertex();
v.x = 200+Math.random()*300;
v.y = 100+Math.random()*200;
vertices[i] = v;
addChild(v);
v.addEventListener(MouseEvent.MOUSE_DOWN, drag);
v.addEventListener(MouseEvent.MOUSE_UP, sdrag);
}
Drawing the model
In the beginning, we have vertices on random positions. Now we do iterations, in each of them we re-count new position of this vertex towards other vertices and it's edges. We do iterations, until a kinetic energy of the network decreases under some limit. In example below, I don't have any limit, I do iterations "onEnterFrame", so theoretically it never stops. "200" and "0.06" are just constants and you can change them to change repulsion and attraction.function onEF(e:Event):void
{
for(i=0; i < n; i++) // loop through vertices
{
var v:Vertex = vertices[i];
var u:Vertex;
v.net_force.x = v.net_force.y = 0;
for(j=0; j < n; j++) // loop through other vertices
{
if(i==j)continue;
u = vertices[j];
// squared distance between "u" and "v" in 2D space
var rsq:Number = ((v.x-u.x)*(v.x-u.x)+(v.y-u.y)*(v.y-u.y));
// counting the repulsion between two vertices
v.net_force.x += 200 * (v.x-u.x) /rsq;
v.net_force.y += 200 * (v.y-u.y) /rsq;
}
for(j=0; j < n; j++) // loop through edges
{
if(!edges[i][j])continue;
u = vertices[j];
// countin the attraction
v.net_force.x += 0.06*(u.x - v.x);
v.net_force.y += 0.06*(u.y - v.y);
}
// counting the velocity (with damping 0.85)
v.velocity.x = (v.velocity.x + v.net_force.x)*0.85;
v.velocity.y = (v.velocity.y + v.net_force.y)*0.85;
}
for(i=0; i < n; i++) // set new positions
{
v = vertices[i];
if(v.isDragged){ v.x = mouseX; v.y = mouseY; }
else { v.x += v.velocity.x; v.y += v.velocity.y; }
}
// drawing edges
graphics.clear();
graphics.lineStyle(3, 0x333333);
for(i=0; i < n; i++)
{
for(j=0; j < n; j++)
{
if(!edges[i][j]) continue;
graphics.moveTo(vertices[i].x, vertices[i].y);
graphics.lineTo(vertices[j].x, vertices[j].y);
}
}
}
You should put a gravity when there are disconnected component.
November 30th, 2010i.e. 4 vertices and 2 edges. in this way they go far away, if you apply a sort of gravity they should stay close together
I think I know what you mean. Just to turn off an antigravity between different components. But then the position of components to each other would be absolutely random, so it will not look very nice. If I add a gravity, they will cover each other, so it will look very strange.
December 2nd, 2010How do you calculate the repulsive and and attractive forces in 3d?
December 3rd, 2010Thanks.
Isaac
It is the same as in 2d. You just add a third coordinate. You can calculate forces in 4d, 5d, 6d … in absolutely the same way.
December 3rd, 2010The variable “rsq” is a squared distance between two vertices in your (probalby euclidean) space. You can find out more on the wikipedia link above.
Thanks. I just did.
December 3rd, 2010Do you have the code avaiable?
December 3rd, 2010No, I want people to do it themselves, it is not so hard. But if you want, I can sell it to you.
December 6th, 2010How much would you charge for that? It’s what I need for a project at my job, and I can’t seem to recreate it!
December 8th, 2010Thanks for this
the code isn’t hard to implement but it’s nice to have a version I can quickly test with reasonable values for the constants 
January 15th, 2011There was one alteration I made with it in the end. For graphs with a single cluster of points and a long tail, the tail edges got really long (it also resulted occasionally in triangles looking like single lines) so I added in an extra force that was given a ‘target edge size’ and applied forces to the vertices to bring them closer to this desired edge side. This gives the graphs a little more body, and stops things from getting stretched too much.
January 15th, 2011Hi, it’s very cool,
Do you have the code avaiable?
Good job
January 31st, 2011this so cool which program did u use
can I get the code
can you give me your email please ?
February 3rd, 2011increpare could you give me your email please ?
February 3rd, 2011Jime: I used Adobe Flash to create it. You can use any platform and language, which allows you to create some grapihcal output. The algorithm is described above.
February 8th, 2011I am trying to create something similar to this but it would create the vertices and edges with the stroke of the mouse any suggestions? basically this http://en.nicoptere.net/ but instead of creating brush strokes it would create a design with the connected line and dot srings
May 13th, 2011jackley: What exatly do you need? Drawing some beziér curves from mouse track?
May 16th, 2011hi,
I think Jackley was talking more specifically about this: http://en.nicoptere.net/?p=476 ; how to render the graph with a distorted picture rather than sticks and modes.
it would mean changing the drawing method, finding “closed” shapes and single lines but it could be nice.
nice blog btw, cool stuff
May 19th, 2011hi, @ Ivan im planning do to that using Java language do think is it easy ?
any advice can help with that ?
can I use some parts of your code ( above )
Thanks
June 22nd, 2011Hello Jime, yes you can. It will be very similar in Java as in Flash.
June 22nd, 2011How can I draw Multigraphs with this ? loops and multiple edges!
January 22nd, 2012hi Michel, I have never heard about multigraphs and I am reading about it on wikipedia right now.
You can do it simply by incidence matrix made of integers, which mean number of edges between two vertices. Then draw several different arcs between two vertices, instead of one line.
I was drawing oriented graphs with arcs in my SM Tool (you need Silverlight plugin to see it).
January 23rd, 2012Was thinking about multigraphs too.. would anything change in the calculation of the forces though ? the attraction should be greater when there are more edges between two vertices, shouldn’t it ?
February 8th, 2012I didn’t try it yet, but my novice approach would be just using the number of edges between two vertices as a factor to multiply with. Would that work ? any better ideas ?
[...] I coded my visualisation using XNA - probably an odd choice but it makes drawing in 2D pretty easy and I had some experience with it. I grabbed JSON data from StoneDonkey’s API, and drew it using pretty much the simplest algorithm I could find. [...]
March 19th, 2012Good implementation. Can you share all project files?
March 22nd, 2012Hi, i’ve been recently implementing such an algorithm but in c# and there the coordinate system is starting in top left corner, y go down positive, and x right positive, and it’s just not working for me
do you have any suggestions that might help me ?
June 19th, 2012Hello,
The coordinate system in flash is the same. You can also check the JavaScript version.
I have implemented this algorithm in 6 or 7 languages including C#. I am sure you just have some minor mistake – plus instead of minus or something. Look at it again, carefully!
June 19th, 2012How die you implement the extra force to not let the nodes move too far away from each other? Lets say with a given distance to each other?
November 25th, 2012Hi,
November 26th, 2012just add a simple condition – if edge length is out of boundaries, then put it back to boundaries.
But note, that if you set too small bounaries, e.g. you set constant edge length L, many graphs can not be drawn this way.