Saturday, May 04, 2013

Self Organising Fun : A Force Directed Graph in CoffeeScript


Emergent Self Organising Behaviour using CoffeeScript, JQuery and Processing.js

What is a Force Directed Graph and why bother spending time coding one in CoffeeScript? 
A Force Directed Graph is a collection of nodes and links that self-organises until its nodes are as far apart as possible and the links do not cross. They appeal because self-organisation is just so intrinsically fascinating and, more professionally, because the project allowed me to bring together a whole set of exciting web technologies including CoffeeScript, JQuery, HTML5 and Processing.js.

Before reading any further why not Play with the Force Directed Graph Demo

Or if you really want to blow your mind why not take a look at the innovative and beautiful flocking system based solely on the principles of electromagnetism Electro-Flock: Modelling Flocks using Simple Electro-Magnetism.

They did it all by themselves
How did it turn out? 
I started this project wondering if CoffeeScript would be worth learning and finished it vowing never again to write another line of naked JavaScript. I also found the combination of CoffeeScript and JQuery to be a powerful and elegant solution to the problem of coding against the browser. Finally, using the Processing.js library coupled to an Html5 canvas  tag meant I could tap the GPU of the client's graphics card and so achieve the smooth visualisation of forces and vectors I wanted.


For more information on Force Directed Graphs please see the Definitions and Discussion section below.

Technology Stack

  • Visual Studio 2012 Express
    Free editor. No extensions supported
  • Jurassic Coffee
    A coffescript compiler and linker. I run it as a build event.
  • CoffeeScript
    The shorter, better version of javascript
  • JQuery
    A javascript library for dealing with the browser DOM
  • Processing.js
    A javascript library for high performance 2D drawing onto an html5 Canvas
  • Bootstrap
    A CSS library so I don't have to think about it.
  • html5
    Its got the new Canvas element that allows for modern animation in the browser.

The Demo

The demo allows you play with Force Directed Graphs of various sorts. Here is a quick run-down.

This is very important
The first thing - don't overlook clicking on the screen. This toggles a Mouse attractor on and off. The effect is dramatic as you convert a Force Directed Graph into a poor man's flocking algorithm. Its also handy for generally mixing things up.

The top tool-bar
The first drop-down determines the number of copies of each graph to generate. Each copy will repel the others so multiple copies can introduce some interesting, higher-order patterns.

The second drop-down determines the type of graph to be generated. Each graph type differs in the number of nodes, the interconnections between the nodes and the node mass. The physical constants that determine magnetic repulsion and spring strength remain the same for all.

The third drop-down allows you to change the behaviour of a node as it encounters the edge of the drawing area.

The bottom tool-bar
The Noise drop-down allows you to introduce random noise into the mix. It is known that Force Directed Graphs will often beach themselves on the desolate shores of sub-optimality . These locally optimal solutions trap the pattern close to the globally optimal solution. Randomness can help fix that by jiggling the system to overcome the local optima and allow the system to keep falling towards perfection.

The Springs check-box toggles the springs on and off. How do the nodes act when they are unfettered?

The Magnets check-box toggles the magnetic repulsor fields on and off.

The Help link brings you back to this page.

Resources


  • The Nature of Code by Daniel Shiffman
    This was my number 1 resource. It is well written and engaging but most of all it tells you everything you need to know about vectors, forces, springs and magnets and how to code them up.
  • A Force-Directed Diagram Layout Algorithm
    Another force-directed example this time written in C#. I reckon I probably stole some code from here.
  • Springs
    An example of how to code various springs in Processing.js, the 2D drawing package I used.

Definitions and Discussion

Graph
A picture of an interconnected set of items where each item is represented by a node and each connection by a link.

A simple, static Graph

Force Directed Graph
A graph that self-organises until its nodes are as far apart as possible and the links do not cross. The nodes repulse one another whereas the links act like springs.

A dynamic Force Directed Graph achieves a state of cybernetic balance

No Really, What is a Force Directed Graph?
Imagine a single tennis ball connected to ten otherwise identical balls by equal lengths of string. How to disentangle this?
Triangular tennis balls?

You could take the brute force approach and sit cross-legged unpicking the knots and arranging the balls. Or you could just let the whole thing self-organise until no balls touch and no strings cross.

A globally optimal solution

You may think that a system of tennis balls and string cannot self-organise but that is not true. This system, like all physical systems, will organise itself until it reaches a low-energy state. It will stop self-organising the moment no energy-lowering moves remain, in other words, when every remaining move implies a rise in the energy state of the system.

The problem: For tennis balls and string this final state is vastly more likely to be a tangled mess rather than a pleasing, symmetrical pattern. We could re-engineer the system using exotic materials but doing this in the real world would be impractical.

The trick is to simulate a node-and-link system (a graph) so that its lowest energy state happens to resemble the pattern you want. Such a system should then untangle itself and, as a ball rolls downhill, self-organise toward the desired pattern.

But we don’t want to just define a low energy state and have the system go there. That’s no fun. Instead we want to simulate a real system, albeit one with the impractical physical properties.  It is the nature of these properties, their interactions, and the final dynamic balance point that determines the final pattern. Once modelled we should be able to just sit back and watch as the complex behaviour spontaneously emerges, powered only by the laws of pseudo-thermodynamics.

To achieve this we must replace the tennis balls with imaginary repulsor magnets. The closer these magnets get to each other the greater the repulsive force they feel. The links are replaced with springs. As a link is stretched so it pulls with ever increasing force on the magnets at either end. All that remains is to tweak the strength of the springs and magnets until a nice, critical balance is reached.

A system like this will seek a low energy state just as any real physical system would. The combination of the magnets repelling plus the springs attracting make the system spontaneously untangle and re-order. To stretch the analogy - the system is powered by virtual kinetic energy harvested from virtual potential energy as the system spontaneously tumbles down an imaginary energy gradient. The process stops when the system finally achieves the lowest energy state, which we have cunningly engineered to be both ordered and aesthetically pleasing.

It’s not magic it but it sometimes looks that way. The fascination of watching Force Directed Graphs gracefully disentangle themselves may well stem from the fact that real-life systems overwhelmingly tend not be ordered at low energy states. Disordered states so vastly outnumber ordered states that our evolutionary expectations assume that any non-living system’s low energy state will be disordered, and this is usually correct. However it is not true for Force Directed Graphs and so, as they spontaneously transition from disorder to order they create a strong illusion of purposeful behaviour, sometimes they seem almost eerily life-like.

A Force Directed Graph is therefore a computer representation of an edge-case physical system. It models a system of repulsor-nodes and springy-links with the final shape of the optimally ordered pattern being determined by the interconnections and the precise balance of the opposing forces of attraction and repulsion.

And finally, don't forget to take a look at the exciting electromagnetic flocking system Electro-Flock: Modelling Flocks using Simple Electro-Magnetism.