Using Force-Based Graphs

This is a collection of my experiences using force-based algorithms to draw graphs.

I used this algorithm in the Wiki Spiderweb application.

Here the good points:

  • Easy to implement
  • Natural looking results
  • User interaction is possible
  • Some influence of placement of nodes

Here the problem areas:

  • Computationally intensive: O(n^2)
  • Layout can become jittery and unstable (at least my implementation that uses real elapsed time for the iterations)
  • Difficult to avoid overlapping nodes
  • Nodes can end up very close to each other

Easy to implement

This is the basic implementation:

	public boolean simulate(float time) {
		for (Node node1 : nodes) {
			for (Node node2 : nodes) {
				if (node1 == node2) {
					continue;
				}
				
				float distanceSquare = getDistanceSquare(node1, node2);
				
				float deltaX = node1.x-node2.x;
				float deltaY = node1.y-node2.y;
				
				node1.forceX += repulsionForce * deltaX / distanceSquare;
				node1.forceY += repulsionForce * deltaY / distanceSquare;
			}
		}

		for (Connection connection : connections) {
			float deltaX = connection.node2.x - connection.node1.x;
			float deltaY = connection.node2.y - connection.node1.y;

			float attractionX = attractionForce * deltaX;
			float attractionY = attractionForce * deltaY;

			connection.node1.forceX += attractionX;
			connection.node1.forceY += attractionY;

			connection.node2.forceX += -attractionX;
			connection.node2.forceY += -attractionY;
		}

		boolean moving = false;
		for (Node node : nodes) {
			node.speedX = minAbs(MAX_SPEED, (node.speedX + node.forceX) * damping);
			node.speedY = minAbs(MAX_SPEED, (node.speedY + node.forceY) * damping);
			
			if (node.speedX > NOT_MOVING_THRESHOLD || node.speedY > NOT_MOVING_THRESHOLD) {
				moving = true;
			}

			if (!node.drag && !node.fix) {
				node.x += node.speedX * time;
				node.y += node.speedY * time;
			}

			node.forceX = 0;
			node.forceY = 0;
		}
		
		return moving;
	}

In the Wiki Spiderweb application I have a few modifications to this basic algorithm.
All of these changes modify the repulsion/attraction functions to adapt for some concrete issues I had with small screen estate, overlapping nodes, …

Natural looking results

This is of course a personal opinion, but I like the organic looking results and find the aesthetically pleasing.

Interactive

Since the algorithm is iterative it is easy to implement interaction with the graph as it moves the nodes around.

First we render the nodes after every iteration of the algorithm.
This turns the graph into a dynamic and not something that just presents a final result.

Second we allow the user to drag nodes around.
The algorithm will simply continue to move the other nodes around, which results in a natural looking dragging of the connected nodes.

Some influence of placement of nodes.

The client code does not have much influence about the actual placement of nodes.

One of the few things it can control is the initial placement of new nodes.

In the Wiki Spiderweb application new nodes are initially placed at a random location close to the parent node.
Since they are all very close to each other the new nodes will have a strong repulsion force, which leads to an explosion effect where the new nodes look like an expanding cloud.
The central parent node tends to move very little, since it is equally repulsed from all its child nodes.
Already existing nodes are pushed outwards by the expanding cloud of new nodes.

The current implementation simply randomizes the x,y coordinates inside small boundaries.
The new nodes are therefore initially placed in a small square. This is actually noticeable if there are enough new nodes.
To improve this the new nodes could be placed randomly inside a circular radius instead of a square region.

If the new nodes are of different types (I am planning to add images and grouping nodes for chapters in the Wiki application) it would be possible to place the new nodes
grouped by type.

Computationally intensive: O(n^2)

The basic algorithm is square and the only optimization possible is to make n as small as possible.

The obvious way to do this is to sort the nodes into groups and only run the algorithm with nodes close to each other.

I plan to sort the nodes into quadrants and let the nested loops of a single quadrant iterate over the 8 neighbor quadrants.
If the forces of far away nodes are considered important, the nodes of each quadrant could be aggregated into a single node and only this node would be used for the repulsion function.

Layout can become jittery and unstable

At least my implementation that uses real elapsed time for the iterations shows this behavior.

Adaptive cooling would probably solve this issue.

Difficult to avoid overlapping nodes.

The algorithm treats nodes as points without size.
But in reality I want to show text or images in the nodes, so many of them will overlap each other.

I attempted several modifications of the algorithm to avoid overlapping nodes but was not happy with the results.
These modifications tried to make the repulsion function aware of whether any nodes where overlapping.
Unfortunately did lead to unstable local minimas, so that the graph became jittery and did not find a stable solution.
Maybe a smarter function without any discontinuities would work.

I also plan to investigate the PRISM algorithm as soon as I have time.

Nodes can end up very close to each other.

Graphs with many interconnected nodes can end up with some nodes being forced very close to each other.

This entry was posted in Development and tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *