Force-based graph drawing in AS3

This post will be dedicated to drawing graphs in an aesthetically pleasing way. We will use physics “spring” algorithm, and create real-time simulation.

Updates

Graphs and their drawing

Graphs

A graph is defined by a set of vertices (e. g. ${a, b, c, d}$) and a set of edges, which are the pairs of vertices ($\{ \{ a,b\}, \{b,c\}, \{c,d\}, \{d,a\}\}$). Most of people would draw this graph as a “square”, but there are many ways to draw it. Some of them are “nicer” than others.

What is “nicely” drawn graph

Let’s try to define it. At first, we don’t want vertices to be too close to each other. Edges should have more or less equal length and don’t cross each other too often. We can define a lot of criterias.

Spring model

In this model, we add an “antigravity” to each node. Due this, edges won’t be too close to each other. We add a spring (an attraction power) between vertices, where is an edge between them. After few iterations (re-counting the power values and re-moving vertices to new positions) we will have a nice looking graph.
I just implemented the algorithm described in this article on Wikipedia.

Vertex class

package
{
   import flash.display.Sprite;
   import flash.geom.Point;
 
   public class Vertex extends Sprite
   {
      // speed of vertex
      public var velocity:Point = new Point(); 
      // force twards other vertices in the network
      public var net_force:Point = new Point();
      public var isDragged:Boolean = false;  // I can drag the vertex

      public function Vertex():void
      {
         // I draw a ring into the middle
         with(graphics)
         {
            beginFill(0xFF005E);
            drawEllipse(-12, -12, 24, 24);
            endFill();
         }
      }

   }
}

Creating a graph

   // set of vertices
   vertices = new Vector.< Vertex >(n, true);
   // set of edges in symetric incidence matrix
   edges = new Vector. < Vector.< Boolean >>(n, true);
   for(i=0; i < n; i++) edges[i] = new Vector.< Boolean >(n, true);
   while(e > 0) // add some edges
   {
      var a:int = Math.floor(Math.random()*n);
      var b:int = Math.floor(Math.random()*n);
      if(a==b || edges[a][b])continue;
      edges[a][b] = true;
      edges[b][a] = true;
      e--;
   }
   // creating vertices
   for(i=0; i < n; i++)
   {
      var v:Vertex = new Vertex();
      v.x = 200+Math.random()*300;
      v.y = 100+Math.random()*200;
      vertices[i] = v;
      addChild(v);
      v.addEventListener(MouseEvent.MOUSE_DOWN, drag);
      v.addEventListener(MouseEvent.MOUSE_UP, sdrag);
   }

Drawing the model

In the beginning, we have vertices on random positions. Now we do iterations, in each of them we re-count new position of this vertex towards other vertices and it's edges. We do iterations, until a kinetic energy of the network decreases under some limit. In example below, I don't have any limit, I do iterations "onEnterFrame", so theoretically it never stops. "200" and "0.06" are just constants and you can change them to change repulsion and attraction.
function onEF(e:Event):void
{
   for(i=0; i < n; i++) // loop through vertices
   {
      var v:Vertex = vertices[i];
      var u:Vertex;
      v.net_force.x = v.net_force.y = 0;
      for(j=0; j < n; j++) // loop through other vertices
      {
         if(i==j)continue;
         u = vertices[j]; 
         // squared distance between "u" and "v" in 2D space
         var rsq:Number = ((v.x-u.x)*(v.x-u.x)+(v.y-u.y)*(v.y-u.y));
         // counting the repulsion between two vertices 
         v.net_force.x += 200 * (v.x-u.x) /rsq;
         v.net_force.y += 200 * (v.y-u.y) /rsq;
      }
      for(j=0; j < n; j++) // loop through edges
      {
         if(!edges[i][j])continue;
         u = vertices[j];
         // countin the attraction
         v.net_force.x += 0.06*(u.x - v.x);
         v.net_force.y += 0.06*(u.y - v.y);
      }
      // counting the velocity (with damping 0.85)
      v.velocity.x = (v.velocity.x + v.net_force.x)*0.85; 
      v.velocity.y = (v.velocity.y + v.net_force.y)*0.85; 
   }
   for(i=0; i < n; i++) // set new positions
   {
      v = vertices[i];
      if(v.isDragged){ v.x = mouseX; v.y = mouseY; }
      else { v.x += v.velocity.x; v.y += v.velocity.y; }
   }
   // drawing edges
   graphics.clear();
   graphics.lineStyle(3, 0x333333);
   for(i=0; i < n; i++)
   {
      for(j=0; j < n; j++)
      {
         if(!edges[i][j]) continue;
         graphics.moveTo(vertices[i].x, vertices[i].y);
         graphics.lineTo(vertices[j].x, vertices[j].y);
      }
   }
}

Old comments (closed because of spam)

30 Comments

  1. Stefano said:

    You should put a gravity when there are disconnected component.
    i.e. 4 vertices and 2 edges. in this way they go far away, if you apply a sort of gravity they should stay close together

    November 30th, 2010
  2. Ivan Kuckir said:

    I think I know what you mean. Just to turn off an antigravity between different components. But then the position of components to each other would be absolutely random, so it will not look very nice. If I add a gravity, they will cover each other, so it will look very strange.

    December 2nd, 2010
  3. Isaac said:

    How do you calculate the repulsive and and attractive forces in 3d?
    Thanks.
    Isaac

    December 3rd, 2010
  4. Ivan Kuckir said:

    It is the same as in 2d. You just add a third coordinate. You can calculate forces in 4d, 5d, 6d … in absolutely the same way.
    The variable “rsq” is a squared distance between two vertices in your (probalby euclidean) space. You can find out more on the wikipedia link above.

    December 3rd, 2010
  5. Isaac said:

    Thanks. I just did.

    December 3rd, 2010
  6. Isaac said:

    Do you have the code avaiable?

    December 3rd, 2010
  7. Ivan Kuckir said:

    No, I want people to do it themselves, it is not so hard. But if you want, I can sell it to you.

    December 6th, 2010
  8. Felix said:

    How much would you charge for that? It’s what I need for a project at my job, and I can’t seem to recreate it!

    December 8th, 2010
  9. increpare said:

    Thanks for this :) the code isn’t hard to implement but it’s nice to have a version I can quickly test with reasonable values for the constants :)

    January 15th, 2011
  10. increpare said:

    There was one alteration I made with it in the end. For graphs with a single cluster of points and a long tail, the tail edges got really long (it also resulted occasionally in triangles looking like single lines) so I added in an extra force that was given a ‘target edge size’ and applied forces to the vertices to bring them closer to this desired edge side. This gives the graphs a little more body, and stops things from getting stretched too much.

    January 15th, 2011
  11. Rich said:

    Hi, it’s very cool,
    Do you have the code avaiable?

    Good job

    January 31st, 2011
  12. Jime said:

    this so cool which program did u use

    can I get the code

    can you give me your email please ?

    February 3rd, 2011
  13. Jime said:

    increpare could you give me your email please ?

    February 3rd, 2011
  14. Ivan Kuckir said:

    Jime: I used Adobe Flash to create it. You can use any platform and language, which allows you to create some grapihcal output. The algorithm is described above.

    February 8th, 2011
  15. jackley said:

    I am trying to create something similar to this but it would create the vertices and edges with the stroke of the mouse any suggestions? basically this http://en.nicoptere.net/ but instead of creating brush strokes it would create a design with the connected line and dot srings

    May 13th, 2011
  16. Ivan Kuckir said:

    jackley: What exatly do you need? Drawing some beziér curves from mouse track?

    May 16th, 2011
  17. nicoptere said:

    hi,
    I think Jackley was talking more specifically about this: http://en.nicoptere.net/?p=476 ; how to render the graph with a distorted picture rather than sticks and modes.
    it would mean changing the drawing method, finding “closed” shapes and single lines but it could be nice.

    nice blog btw, cool stuff :)

    May 19th, 2011
  18. Jime said:

    hi, @ Ivan im planning do to that using Java language do think is it easy ?
    any advice can help with that ?
    can I use some parts of your code ( above )

    Thanks

    June 22nd, 2011
  19. Ivan Kuckir said:

    Hello Jime, yes you can. It will be very similar in Java as in Flash.

    June 22nd, 2011
  20. Michel Kogan said:

    How can I draw Multigraphs with this ? loops and multiple edges!

    January 22nd, 2012
  21. Ivan Kuckir said:

    hi Michel, I have never heard about multigraphs and I am reading about it on wikipedia right now.

    You can do it simply by incidence matrix made of integers, which mean number of edges between two vertices. Then draw several different arcs between two vertices, instead of one line.

    I was drawing oriented graphs with arcs in my SM Tool (you need Silverlight plugin to see it).

    January 23rd, 2012
  22. uli said:

    Was thinking about multigraphs too.. would anything change in the calculation of the forces though ? the attraction should be greater when there are more edges between two vertices, shouldn’t it ?
    I didn’t try it yet, but my novice approach would be just using the number of edges between two vertices as a factor to multiply with. Would that work ? any better ideas ?

    February 8th, 2012
  23. Malcolm Crum said:

    [...] I coded my visualisation using XNA  - probably an odd choice but it makes drawing in 2D pretty easy and I had some experience with it. I grabbed JSON data from StoneDonkey’s API, and drew it using pretty much the simplest algorithm I could find. [...]

    March 19th, 2012
  24. miqbal said:

    Good implementation. Can you share all project files?

    March 22nd, 2012
  25. graphss said:

    Hi, i’ve been recently implementing such an algorithm but in c# and there the coordinate system is starting in top left corner, y go down positive, and x right positive, and it’s just not working for me :( do you have any suggestions that might help me ?

    June 19th, 2012
  26. Ivan Kuckir said:

    Hello,
    The coordinate system in flash is the same. You can also check the JavaScript version.

    I have implemented this algorithm in 6 or 7 languages including C#. I am sure you just have some minor mistake – plus instead of minus or something. Look at it again, carefully! :)

    June 19th, 2012
  27. Tomo said:

    How die you implement the extra force to not let the nodes move too far away from each other? Lets say with a given distance to each other?

    November 25th, 2012
  28. Ivan Kuckir said:

    Hi,
    just add a simple condition – if edge length is out of boundaries, then put it back to boundaries.
    But note, that if you set too small bounaries, e.g. you set constant edge length L, many graphs can not be drawn this way.

    November 26th, 2012
  29. jsとcanvasでグラフの描画(力学モデル)を実装した | WEB EGG said:

    [...] » Force-based graph drawing in AS3 ツイート (adsbygoogle = window.adsbygoogle || []).push({}); [...]

    December 20th, 2013
  30. Algorithm to minimize vertex distances - Dwarf Fortress - Tech Forum Network said:

    [...] I have found implementation of the Force draw algorithm in AS3 (the web contains JS version too). I will try to convert it to discrete version. But I have [...]

    January 24th, 2014