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

# Why you should go to the Business of Software Conference Next Year

Most people, having already paid $2000.00 of their hard earned money, and then having flown, driven, or otherwise travelled to Boston to attend a conference, and then having paid an additional $250/night plus $33/night parking and "tourism taxes" to the Seaport Hotel -- most people, after all this, are unlikely to say that it was a waste of time and they should have stayed home watching the remaining salvaged episodes of*Doctor Who*on Netflix.

In fact, I found it quite useful.

# How IE <canvas> tag emulation works

At the time of this writing, Internet Explorer at version 8.0 still lacks the <canvas> tag. But you can easily add the capability by including a short javascript file in your page. At first glance, that's astounding. How do you implement an entire vector graphics API in a few lines of Javascript?# Keeping Abreast of Pornographic Research in Computer Science

Burgeoning numbers of Ph.D's and grad students are choosing to study pornography. Techniques for the analysis of "objectionable images" are gaining increased attention (and grant money) from governments and research institutions around the world, as well as Google. But what, exactly, does computer science have to do with porn? In the name of academic persuit, let's roll up our sleeves and plunge deeply into this often hidden area that lies between the covers of top-shelf research journals.# Free, Raw Stock Data

Scraping financial information is easy with my friend, python.# Creating portable binaries on Linux

Distributing applications on Linux is hard. Sure, with modern package management,*installing*software is easy. But if you are

*distributing*an application, you probably need one Windows version, plus umpteen different versions for Linux. In this article, we'll create a dummy application that targets the following operating systems, which are commonly used in business environments...

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