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

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*.

Great webpage!

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 :)

# Email Etiquette

If you begin your emails with "Hi, <name>!" then they will seem less rude.# A Rhyming Engine

Here's a rhyming engine, written in 1000 lines of C++ code. It uses the freely available Moby dictionary, and full source code is provided.# Yes, You Absolutely Might Possibly Need an EIN to Sell Software to the US

After many months, your software sale is complete! You've got a purchase order, sent the invoice, delivered the software. You're already handling some support issues from users at BigCorp. Then BANG! Martha from Procurement emails back, as a favour, just to let you know that BigCorp has not received your W8 form with a valid tax id, and therefore will be withholding 30% of the purchase price of your multi-thousand dollar product for taxes.# Finding Bieber: On removing duplicates from a set of documents

Using a locality sensitive hash, you can mark duplicates in millions of items in no time.# Finding the top K items in a list efficiently

Do you use sort() to find the top results? Here's a simple trick that will make your software run much faster.# Zwibbler: A simple drawing program using Javascript and Canvas

Now it's a commercial product, but Zwibbler was once a fun side-project, and here's some details on its implementation.# You don't need a project/solution to use the VC++ debugger

You learn a lot of things on the job as a programmer. Years ago, at my first coop position, I was a little confused when my boss went to Visual C++, and tried to open the .EXE file as a project.*What a dolt!*I thought.

*That's not going to work.*

Steve Hanovmakes a living working on Rhymebrain.com, PriceMonkey.ca, www.websequencediagrams.com, and Zwibbler.com. He lives in Waterloo, Canada.