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]. We pretend that the nodes on the graph all strongly repel each other. However, on the other hand, nodes that are connected attract each other with a weaker force. It is as if you had a bunch of statically charged styrofoam balls connected with springs, and its very fun to watch.

Click the image to reset it.

Here's the code that moves the nodes around.

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;
    }
};

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.