Force-Directed Graph Layout With Proce55ing
(click on image to view the applet)
In a previous post, I mentioned something about implementing touchgraph-like graph rendering with Proce55ing. Today I will attempt to build credibility with my precious audience by actually doing what I said I was going to do. You know, it builds character and credibility and shit.
The applet I’ve posted today demonstrates the groundwork from which I will build my next few applets. It’s interactive, so you can click and drag nodes around. Hit the spacebar to generate a new random set of nodes and edges. Other than that, it’s totally featureless.
You may wonder why I’m not just using the Touchgraph code. There are a number of reasons. The first is threading. Touchgraph does the the layout algorithm in a thread that runs separately from the ui rendering loop. THREADSAFE CODE IS HARD TO WRITE. And I lack the discipline to get it right. Another reason is that it’s got an awkward API (to me personally; I make no judgements and consider API design to be more art than analysis or synthesis). My final and most important reason not to use Touchgraph is a severe case of NIH. I wanted to write it all myself. :)
Primary Considerations
- The choice of layout algorithm: Needs to be relatively fast because my intention is to build interactive applets that arrange edges and nodes in realtime. Simplicity is also a premium- I’d like it to be easy to implement because I’m mentally lazy.
- The data model: Try to present as simple a representation of nodes and edges as possible, and allow easy access to nodes from edges, to edges from nodes and get answers to basic questions like “hey are these two nodes connected”?
- Proce55ing-Friendly: doesn’t molest AWT or Swing.
The Algorithm: There is roughly a metric shitload of options from which to choose a graph layout algorithm, but the one I find simplest to implement (and most intuitive for end users) is the force-directed method. This is the same method used by Touchgraph. Force-directed graph layout borrows equations from physics to simulate springs and reverse-gravity (antigravity, you might say). With this method, edges are treated as though they were springs, and nodes are treated as though they are massive bodies.
The spring force equation:
F = stiffness * (currentLength – naturalLength)
(heh heh, stiffness. natural length. ahem. anyways) The spring wants to be a certain length and whenever it’s not that length there’s a force proportional to how much it’s compressed or stretched beyond it’s natural length pushing it back. In my implementation, edges can have distinct natural lengths. This is useful when you want to represent the different strengths of relationships as distance between two nodes.
The amount of time it takes to calculate all the spring forces is directly proportional to the number of edges. Adding edges doesn’t hurt much, time-wise.
Nodes are modelled in Bizarro World, where gravity works in reverse.
The gravitational equation:
F = G*(m1*m2)/r^2.
That was Newton, right? Maybe Kepler? Anyhoo, r is the linear distance between two nodes. The closer two nodes get, the more they repel eachother. That also happens to be a fairly accurate way to describe most of my personal relationships. m1 and m2 are the masses of the two nodes. In my implementation, nodes may have different masses, and that can be used to represent data set attributes orthogonally to the strenth of edges between nodes.
Due to the N-body-problem-ness of gravity simulations, and my wanton ignorance of methods numerical that surely address the problem, the gravitational portion of the force calculations is relatively painful. The time required to calculate antigravitational forces is proportional to the square of the number of nodes. Ways to speed this up is an active research area.
[The above paragraph contains a reference to wikipedia, so that's minus one point. Later on though it links to citeseer, so that's plus one point. Final score: zero.]
Those are the two forces that push the nodes around. Dragging a node with the mouse trumps all forces from other nodes or edges.
Rendering
I love alpha blending. I don’t know why. I think it may just be a gratuitous indulgence that I’ll grow out of someday, but for now I’m fadin’-in and fadin’-away. Edges have different thicknesses, and this thickness is determined by how short the edge wants to be. Thick Edge = Wants to be Short. The nodes are rendered as circles whose radius is determined by the mass of the node. Big Node=Massive, Repugnant Node That Everybody Runs Away From.
The main loop of the app does the following twenty times every second:
for each node in the graph add up the spring forces applied by the node's edges using the spring force equation add up the effects of gravity from every other node (ouch) add those forces up and apply them to the node's current position draw all the edges draw all the nodes
The API
Like I said, it’s dirt simple. The one nicety that I have in this revision is that you can select nodes. At any point in time you can ask the Graph object for the currently selected node (if any), the currently moused-over node (if any) and the current dragged node (if any). That enables the nodes to draw themselves differently in each of those cases. Next rev I’ll probably have the same events for Edges as well.
At this point I think I’ve spent more time blabbing about this thing than actually writing the code.
Heya, SoCC.
Just found your site via processing and really dig what you’re doin. Also like the humor in the text.
I’m also into 3d graphical representation of dynamic node motion as a information model. And although I’ve got big ideas about how to make a cool structure, by programming is slow to keep up.
Anyhow, I like what your doing and find it helpful in my own work. Thanks of the open sharing!
Dave
David Montie
11 Dec 05 at 9:35 pm
David,
Thanks for dropping by. Looks like you’re working on some pretty interesting stuff yourself. I’ve got a lot more ideas than time to code them too. I’m glad you got both the technical content and the humor of this post. I strive for both but I’m happy if I hit either of them.
As far as 3D goes, the vector class I’m using has a z-component. I just don’t use it currently. There are some cool things you can do with the z-axis in graph layout. For one thing, you don’t have to worry about edge crossing or planarity. The graph can be rotated to a position where things make more sense. I have seen some implementations of Force-Directed graph layout algorithms in 3D but I don’t have any links handy.
Oh and of course feel free to use my source code. I haven’t gotten around to plastering Creative Commons lisences all over it yet, but will do so in the next revision.
banksean
11 Dec 05 at 11:36 pm
um. mr. techie? why doesn’t it work on my computer?
CJ
13 Dec 05 at 12:31 am
because your a retard
banksean
13 Dec 05 at 8:12 am
or maybe ‘half-retard(ed)’ like the new Soft Boy CD. CD, wow i said it. i’m really embracing technology now.
brent
13 Dec 05 at 10:18 pm
records made into cassetes
and compact discs
such tiny holes
and it still skips
some times
dadadadadadadadadadadadadadadad
banksean
13 Dec 05 at 10:25 pm
My fav use of a type of graph similar to this is the visual thesaurus: http://www.visualthesaurus.com
Fun stuff.
Shannon
20 Jan 06 at 11:35 pm
Thanks so much! Been looking for a force-directed graph for Processing (there was one as part of a physics lib, but it didn’t support interaction).
This is perfect for my (super secret operation) / next little project.
tom
16 Dec 06 at 5:55 pm
Hi, and thanks for this applet, it’s really nice to play with by simply changing the function
F = stiffness * (currentLength - naturalLength)
with other sin/cos/tan etc. code, it produces bizarre and interesting movements.
I was wondering if there’s a maximum of nodes it can handle, because if I create more than, say, around 200 nodes it disappears just after having been drawn. If I push the space bar, it is redrawn and it disappear again. Any ideas?
Thanks again and go on!
carlo
4 Jul 07 at 5:32 pm
I’ve got a more up-to-date version of this lib/applet here: http://www.cricketschirping.com/weblog/?p=966
It uses a more performant set of calculations (runge-kutta) that should handle more nodes than this version. The basic interface to the Graph/Node classes is very similar though.
banksean
5 Jul 07 at 9:28 am
Just a thought. Your gravity formula: it should really only be r^2 when simulating three-dimensional space. In a hypothetical 2D world, as per your simulation, gravity - like light intensity - should fall off linearly with distance (the emanating photons/gravitons are distributed around the perimiter of an increasingly large notional circle surrounding each massive body, as opposed to the surface of a notional sphere). I appreciate this is all a bit hypothetical given that you’re not trying to simulate the real world (and especially not a bizarre 2D version of it which doesn’t actually exist) but I thought it might be interesting to see what difference it makes to the behaviour of your simulation?
Justin Washtell
19 Jul 07 at 6:53 pm
Sorry, I’m writing this as I’m discovering it. Your app is kinda in 3D, but the movement is restricted to the plane, am I correct? Anyway, you can very quickly and massively optimise your gravitation routine by making the inner loop “for(j=i+1…” rather than “for(j=0…” that will half the number of comparisons as you suggest… and also getting rid of the SQRT in there, which you only multiply back out again afterwards because you are interested in the square of the distance (unless you were to try the experiment I mentioned above).
Justin Washtell
19 Jul 07 at 7:10 pm
Oh dear, you’ve actually looked at the source. [runs away]
banksean
19 Jul 07 at 7:17 pm
Hello. My name is Kate. I wish to become Striptease. I constantly train.
I have removed video and I wish you to ask to look it and to tell to me about my errors, or to prompt, as I can improve the technics.
[url=]http://cananecatah.blogspot.com[/url]
Thank you.
KattyS
1 Oct 08 at 11:31 pm
Hey… I am interesting in learning how to do a force directed graph with Processing and your example is one of the better ones. Is there anyway you can email the data files. That way I have a compilable foundation?
Dennis
26 Oct 09 at 6:41 pm
Hi,
i am in about the same situation as dennis. I am interested in graphs and i am learning processing and having your data files would be very helpful to understand how to define the graph.
thx,
stefanK
8 Nov 09 at 4:31 pm
I was having trouble getting my own graph to layout properly, so I’ve just ported yours to Java, and am using it. Thanks!
Russell Jurney
2 Dec 09 at 4:10 am
Name=http://techno-internet.blogspot.com/
New gadgets and devices,computers and last technologies=all about internetall about internethttp://techno-internet.blogspot.com/url=http://techno-internet.blogspot.com/all about internet[/url]
Mail=rino@yahoo.com Country=italy
Age=35
City=arko
ICQ=112585741
Job=Engineer
Phone=991847211123
Title=computers and technologies
worrons
28 Aug 10 at 7:53 pm