While graphs are inherently difficult to layout pleasantly, algorithms
based on the physical concept of force often yield good results.
In this post, I’m going to implement such an algorithm
from scratch while motivating each step in the process.
Consider the following screenshot.
First, we need to get the rectangles (called nodes from here on) apart.
To do that, we’re going to make the nodes repel each other by
applying a repulsion force to each pair of nodes.
Here we simply calculate the distance between each pair of nodes
and move the two nodes of the pair apart by adding a force to each node
that points away from the other node. The bigger the distance between
two nodes, the smaller the force applied.
If the nodes are at exactly the same position though, both delta and
distance will be 0 thus this will not work. Instead, we simply add a small
force into a random direction to drive the nodes apart.
This is better, but you can see that related (linked) nodes are all over the place.
We want nodes that are linked to be closer together than to other nodes.
Thus, we need a force that makes linked nodes attract each other.
Wow, they are getting cozy! This isn’t bad but if I was a node I would prefer
to have a little more space for myself. Let’s replace the attraction force with
a spring force.
Much better, now this looks almost beautiful!
However, the brown node in the
top is trying to escape. The purple one below it is not far behind. Not so fast!
We apply a center force that makes every node wanna be the center of attention.
The bigger the distance between the node and the center of the window,
the larger the force urging it back.
Excellent! Now that we have gathered our forces, how do we use them to move objects around?
Here’s how to update the objects’ positions.
As you can see, we limit how far a node can be displaced at a time,
otherwise a large force might cause it to overshoot the node’s desired position.
All this talk about nodes, but what are they?
Who creates them?
This class is designed to be reusable and makes no assumptions about the objects passed to it.
Instead, you need to pass functions that tell the class how to deal with your objects.
And how do you use it with your own objects? Here’s an example with pygame.
Let’s not forget the imports.
And a little helper function.
That’s it! I leave it to you to assemble the code in the correct order.