Drawing Graphs with Physics
I use graphviz whenever I need to draw state machine diagrams. Drawing circles connected with lines is a hard problem for computers, because they have to decide where to place the circles so the diagram makes sense. These types of diagrams are called graphs.
To my surprise, I found that there is a very simple way to arrange graphs that can be expressed in only a few lines of code, using force-directed placement [Fruchterman, 1991].
Click the image to reset it.
Here's the code that moves the nodes around.
Its really fun to play with this method. Here's what happens if we add a bit of gravity to the system. (Click to reset)
Coding that made me want to play The Incredible Machine.
Springs.prototype.recalc = function()
{
var width = this.ctx.canvas.width;
var height = this.ctx.canvas.height;
// K is related to how long the edges should be.
var k = 200.0;
// C limits the speed of the movement. Things become slower over time.
var C = Math.log( this.frame + 1 ) * 100;
this.frame++;
// calculate repulsive forces
for ( var vindex = 0; vindex < this.graph.nodes.length; vindex++ )
{
var v = this.graph.nodes[vindex];
// Initialize velocity to none.
v.vx = 0.0;
v.vy = 0.0;
// for each other node, calculate the repulsive force and adjust the velocity
// in the direction of repulsion.
for ( var uindex = 0; uindex < this.graph.nodes.length; uindex++ )
{
if ( vindex == uindex ) {
continue;
}
var u = this.graph.nodes[uindex];
// D is short hand for the difference vector between the positions
// of the two vertices
var Dx = v.x - u.x;
var Dy = v.y - u.y;
var len = Math.pow( Dx*Dx+Dy*Dy, 0.5 ); // distance
if ( len == 0 ) continue;
var mul = k * k / (len*len*C);
v.vx += Dx * mul;
v.vy += Dy * mul;
}
}
// calculate attractive forces
for ( var eindex = 0; eindex < this.graph.edges.length; eindex++ )
{
var e = this.graph.edges[eindex];
// each edge is an ordered pair of vertices .v and .u
var Dx = e[0].x - e[1].x;
var Dy = e[0].y - e[1].y;
var len = Math.pow( Dx * Dx + Dy * Dy, 0.5 ); // distance.
if ( len == 0 ) continue;
var mul = len * len / k / C;
var Dxmul = Dx * mul;
var Dymul = Dy * mul;
// attract both nodes towards eachother.
e[0].vx -= Dxmul;
e[0].vy -= Dymul;
e[1].vx += Dxmul;
e[1].vy += Dymul;
}
// Here we go through each node and actually move it in the given direction.
for ( var vindex = 1; vindex < this.graph.nodes.length; vindex++ )
{
var v = this.graph.nodes[vindex];
var len = v.vx * v.vx + v.vy * v.vy;
var max = 10;
if (this.frame > 20) max = 2.0;
if ( len > max*max )
{
len = Math.pow( len, 0.5 );
v.vx *= max / len;
v.vy *= max / len;
}
v.x += v.vx;
v.y += v.vy;
}
};
I noticed the performance problems right away, which is why the example is small. I'm reading about some methods for improving the performance using "multipole" force calculations, which summarize the effects of distant groups of particles into a single force, and KD-Trees, which allow fast lookup to form these groups.
It's also one which can be quite problematic to get right, as it's a performance hog in dense graphs, also because it's sometimes a bit hard to get a finite state quickly (so the nodes are moved around for longer than the user might want to wait for it). Of course it's also the most coolest way to layout a graph ;) The examples look great :)
Optimizing Ubuntu to run from a USB key or SD card
Fortunately, by following the tips below, you can make your USB or SD card based linux system fly!Give your Commodore 64 new life with an SD card reader

The simple and obvious way to walk through a graph
At some point in your programming career you may have to go through a graph of items and process them all exactly once. If you keep following neighbours, the path might loop back on itself, so you need to keep track of which ones have been processed already.When a reporter mangles your elevator pitch
If a reporter asks you about your new startup company, be careful what you say.UMA and free long distance
What's to stop me from travelling to another continent, and then making free long distance calls to local numbers back home? Technically, nothing.Installing the Latest Debian on an Ancient Laptop
