Force-based graph drawing

Hi again!

This time I will show you how my simple implementation of force-based graph drawing looks.

For background information, go to wikipedia's page. My implementation is based on the algorithm outlined there.

Pseudocode

Here is the pseudocode described at wikipedia.org which is used for the implementation:

set up initial node velocities to (0,0)
set up initial node positions randomly // make sure no 2 nodes are in exactly the same position
loop
  total_kinetic_energy := 0 // running sum of total kinetic energy over all particles
  for each node
    net-force := (0, 0) // running sum of total force on this particular node
         
    for each other node
      net-force := net-force + Coulomb_repulsion( this_node, other_node )
    next node
         
    for each spring connected to this node
      net-force := net-force + Hooke_attraction( this_node, spring )
    next spring
         
    // without damping, it moves forever
    this_node.velocity := (this_node.velocity + timestep * net-force) * damping
    this_node.position := this_node.position + timestep * this_node.velocity
    total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2
  next node
until total_kinetic_energy is less than some small number  // the simulation has stopped moving

So, the basic idea is to group connected nodes while still keeping a distance between all nodes in the graph. This, of course, doesn't prevent edges from crossing each other, as it is merely a method for positioning nodes on the plane; however, it turns out that it does quite well visually anyway.

Defining a simple graph

First, given we have access to a class Vector2D, a simple graph consists of nodes defined as follows:

public class GraphNode {
  public List<GraphNode> in = new LinkedList<GraphNode>();
  public List<GraphNode> out = new LinkedList<GraphNode>();

  public Vector2D velocity = new Vector2D(0.0f, 0.0f);
  public Vector2D position = new Vector2D((float) Math.random() * GRAPH_SIZE, (float) Math.random() * GRAPH_SIZE);

  public GraphNode() {
  }
}

Main loop

Next is the main loop. It is a simple implementation of the above pseudocode. Given we have a list containing all nodes in the graph, allNodes, the main loop looks like this:

float totalKineticEnergy = 100.0f;

while (totalKineticEnergy > 0.01f) {
  totalKineticEnergy = 0.0f;

  for (GraphNode node : allNodes) {
    Vector2D netForce = new Vector2D(0.0f, 0.0f);

    for (GraphNode otherNode : allNodes) {
      if (otherNode == node) {
        continue;
      }
      netForce += coulombRepulsion(node, otherNode);
    }

    for (GraphNode otherNode : node.out) {
      netForce -= hookeAttraction(node, otherNode);
    }

    for (GraphNode otherNode : node.in) {
      netForce -= hookeAttraction(node, otherNode);
    }

    node.velocity = (node.velocity + netForce) * (1.0f - DAMPING);
    node += node.velocity;

    totalKineticEnergy += velocity(node) * velocity(node);
  }
}

Calculation of Coulomb Repulsion

Now comes the interesting part: Calculation of Coulomb Repulsion. It is straightforward. Coulomb's Law says:

F = ElectrostaticConstant * ((amp1 * amp2) / difference²

By choosing a suitable constant for electrostatic constant, amp1 and amp2, fx. 0.05, and multiplying by the normalized difference-vector to keep direction, the method looks like this:

private Vector2D coulombRepulsion(GraphNode n1, GraphNode n2) {
  Vector2D difference = n1.subtract(n2);
  float dist = (float) Math.sqrt((difference.x * difference.x) + (difference.y * difference.y));

  if (dist == 0.0f) {
    return 0.0f;
  }

  // (COLULOMB_REPULSION_CONSTANT * (difference / dist)) / (dist * dist);
  return difference.divide(dist)
                   .multiply(COLULOMB_REPULSION_CONSTANT)
                   .divide(dist * dist);
}

Calculation of Hooke's Attraction

Turning to calculation of Hooke's Attraction, this is just as easy. This is the formula used:

F = DifferenceBetweenLocation * ElasticConstant

Choosing an elastic constant, fx. 0.0001, it looks like this:

private Vector2D hookeAttraction(GraphNode n1, GraphNode n2) {
  return n1.subtract(n2) * HOOKE_ELASTIC_CONSTANT;
}

That's it!

Hope it was useful!