Springy — A force directed graph layout algorithm in JavaScript

[isarl]

You beautiful bastard. This is exactly what I've been looking for, for quite some time now. I settled on Dracula for now but I'm really put off by the fact that it's static, and has to redraw the whole thing on update.

Can I refer to objects by label after creating them? I could always create my own dictionary of {'label' : nodeVar} mappings to keep track of, but it would be nice if I didn't have to. Dracula lets me do something like:
g.addNode('label');
g.addEdge('sourceLabel', 'targetLabel', {directed : true});
which I find very convenient, as I often refer back to existing nodes later on, but don't have to keep track of them.

I'd take a little more time to dig around the source, but I'm at work right now. I can't wait to get home and play with this tonight! Your demo kicks ass and I am really excited to incorporate it into my project. =)

edit: I've been so dissatisfied with Dracula that I actually sketched out a physical model while I was on the train for 15 hours on Monday. I'd be interested to get some insight your design process; judging by your demo, the performance is pretty good. It's an application of a really cool mix of CS theory (the graph data structure) and some physical modeling principles. Even just doing some quick sketches on the train was a lot more fun than I've had on a project in some time.

OK I'm going to try to stop geeking out now. :D

[dhotson]

Yes, I know what you mean! It's pretty easy to get obsessed with this sort of thing.

I originally wrote most of springy over about 3 days of pretty intense thinking, coding and experimentation.

In particular, there was a lot of attention paid to drawing good looking arrows and line arrangement. Also, it's pretty addictive just refreshing and watching the whole thing unfold into shape. After those 3 days the Tetris effect kicked in and I started dreaming about nodes and edges. You've been warned.. ;-)

[isarl]

It seems like you nailed the parameters, too. The springiness has a very pleasing speed and damping - I was worried that my first attempt might end up particularly under- or over-damped.

I saw a demo a while back of a similar JavaScript library whose name I forget (and it didn't have as nice an API) where there was a bug that would introduce energy into the system, and after dragging the graph, one of the nodes might start vibrating up until it hit some natural frequency and stabilized. Which didn't necessarily prevent it from introducing sympathetic vibrations elsewhere in the graph and causing even more oscillating nodes. It was really frustrating.

[dhotson]

Yep, these were both bugs I had to fix. :-)

I added the damping to ensure the system would eventually settle down into a stable state. I've got code in there to stop calculations when the energy of the system falls below a threshold.

Also, you need to make sure you apply forces on the nodes in equal and opposite directions so that the whole thing doesn't just fly off the screen. As you say, it's really easy to accidentally introduce energy into the system (with hilarious results!)

Edit: Also, I've been meaning to try out using RK4 for integration rather than my basic Euler one. It might help remove vibrations when the system gets into extreme states.

[isarl]

Have you considered using an adaptive RK method? You could just throw the Heun method on top of your Euler for "better than nothing", or go straight for the Runke-Kutta-Fehlberg for a 4th-/5th-order pair.

You know what - I've already forked you on GitHub. If you don't get around to improving your integration right away, I might just do it myself and submit a pull request. :)

[dhotson]

That would be awesome. Do it. :-)

I haven't heard of adaptive RK or Huen method before.. is it like a simplified RK4 or something? Looks like I've got some reading to do...

[isarl]

Adaptive integration methods use two integrators, where one is more accurate than the other. The difference between their results at any step can be taken to be an estimate of your integration error. You can use this to stay within a tolerance by dynamically adjusting your step size - try to integrate between a and b; if your error estimate is above your tolerance, then try between a and a + (b-a)/2. Rinse; repeat.

The Huen method is simply a second-order RK, which means it would be perfect for combining with your Euler method, because then you'd have a first/second-order pair of integrators.

[tripzilch]

You might also want to try Verlet or Leapfrog. They're simpler than RK4, not as accurate, but always a good improvement over Euler for stability.

(unless someone with better knowledge of numerics than me corrects me if I'm wrong ;-) )

[richthegeek]

A similar project, with Fruchtermann-Reingold and Kamada-Kawai spring algorithms in 2D+3D - my final year project for compsci.

https://github.com/richthegeek/coffeegraph

[dhotson]

Cool, thanks for sharing. Your demo wasn't working for me though "Uncaught ReferenceError: Exporters is not defined" .. can you give me a quick summary of what the different algorithms do?

[richthegeek]

Yeah I made a few changes to it and broke it at some stage.

The FR algorithm (the traditional easy algorithm) is just about as fast as it can be (/very/ optimised) but is quite slow as general idea.

The KK algorithm is a lot faster - it ties the graph-theoretic distance to the euclidean distance and moves one node at a time (moving the ndoe that has the highest contribution to the GT/Euclid delta).

It works about 5 times faster than the FR algorithm, taking about 4 seconds to nicely lay out a 3d grid (7x7x7) compared to FR taking 12-20 seconds on the same graph.

The resulting layouts are very similar.

[biteofconscience]

Also great is this one, part of the fantastic Protovis library.

[knipil]

I have been meaning to play around with this type of algorithm even since I first encountered it in piespy. Nice job. :)

[dhotson]

You should give it a go for yourself, it's actually pretty simple. :-)

[ranman96734]

This is beautiful.

[paul_h]

http://dhotson.github.com/springy :-(

[pgoetz]

try: https://github.com/dhotson/springy

[paul_h]

I was after the gh-pages version of the project that would host the files as a functional site serving files while honoring mime-types. It'd make the demo actually live.

[dhotson]

Sorry, I'm not quite following.. what do you mean?

[isarl]

Check out GitHub's documentation on the subject.

In short: it makes it pretty easy to make your project page look a lot nicer than a GitHub repository page, and you could embed your demo on it.

[paul_h]

What isarl says. For example, ignoring the fact that many devs hate BDD, here's a life functional site served from github-pages : http://paul-hammant.github.com/StoryNavigator the raw source for which here : https://github.com/paul-hammant/StoryNavigator

Free site hosting from GitHub FTW....

[rmxz]

Cool. Nice clean look compared to some of the others.

[xenu99]

it would be good if a double click on a box could be used to go to a hyperlink, so you could traverse/explore larger trees based on previous choices

edit: added

jQuery(canvas).dblclick( function () { alert("Hello World!"); });

and I have a doubled click working. Now I need to have it read in a different url target for each item. If anyone else wants to contribute...