Attraction-Repulsion Algorithm
Or how to layout graph nodes on a canvas using an iterative approach!
Or how to layout graph nodes on a canvas using an iterative approach!
The principle is as follow: two nodes linked by an edge attract themselves, but in the same time the closer two nodes are, the more they repel each other.
At each iteration we start by first adding forces that apply to each node and then we compute the new position.
Please notice that this approach gives better result when the nodes are already approximately placed near their final position (it is great to adjust the final position).
Let’s write some source-code in python
Defining what a node is
Well, let’s just say that a node is something with a center (here represented by x and y coordinates)
import random
from typing import Self
class Node:
def __init__(self, x: float, y: float):
self._x = x
self._y = y
# the vector is initially null
self._vx = 0
self._vy = 0
@classmethod
def from_random(cls) -> Self:
# helper method to get a node at a random position
return cls(random.randrange(10, 110, 1), random.randrange(10, 110, 1))
@property
def x(self) -> float:
return self._x
@property
def y(self) -> float:
return self._y
def add_vector(self, vx: float, vy: float):
self._vx += vx
self._vy += vy
def process_position(self):
self._x += self._vx
self._y += self._vy
# we reset the vectors
self._vx = 0
self._vy = 0How to process the attraction-repulsion between two nodes
import math
NOMINAL_DISTANCE = 40 # expected "perfect" distance between two linked nodes
def process_vector(node_a: Node, node_b: Node, coef: float, linked: bool):
delta_x = node_b.x - node_a.x
delta_y = node_a.y - node_a.y
distance = math.sqrt(delta_x ** 2 + delta_y ** 2)
angle = math.atan2(delta_y, delta_x)
vector = 0
if linked:
# attraction
vector += coef
if distance <= NOMINAL_DISTANCE * 1.5:
# repulsion does not happen when nodes are far from each other
vector -= coef * NOMINAL_DISTANCE / distance
vx = math.cos(angle) * vector
vy = math.sin(angle) * vector
node_a.add_vector(vx, vy)
node_b.add_vector(-vx, -vy)Let’s test it!
Using pillow to draw images
(In a real code you should use loops instead of calling x times process_vector and then process_position)
from PIL import Image, ImageDraw
if __name__ == '__main__':
node_a = Node.from_random()
node_b = Node.from_random()
node_c = Node.from_random()
node_d = Node.from_random()
node_e = Node.from_random()
node_f = Node.from_random()
for n in range(50):
coef = 1.0 - 1.0 * (float(n) / 50.0)
if n % 1 == 0:
im = Image.new('RGB', (120, 120), color=(255, 255, 255))
draw = ImageDraw.Draw(im)
draw.line((node_a.x, node_a.y, node_d.x, node_d.y), fill=(128, 128, 128), width=2)
draw.line((node_a.x, node_a.y, node_e.x, node_e.y), fill=(128, 128, 128), width=2)
draw.line((node_a.x, node_a.y, node_f.x, node_f.y), fill=(128, 128, 128), width=2)
draw.line((node_b.x, node_b.y, node_d.x, node_d.y), fill=(128, 128, 128), width=2)
draw.line((node_c.x, node_c.y, node_d.x, node_d.y), fill=(128, 128, 128), width=2)
draw.ellipse(
(node_a.x - 5, node_a.y - 5, node_a.x + 5, node_a.y + 5),
fill=(128, 0, 0),
outline=(0, 0, 0)
)
draw.ellipse(
(node_b.x - 5, node_b.y - 5, node_b.x + 5, node_b.y + 5),
fill=(0, 128, 0),
outline=(0, 0, 0)
)
draw.ellipse(
(node_c.x - 5, node_c.y - 5, node_c.x + 5, node_c.y + 5),
fill=(0, 0, 128),
outline=(0, 0, 0)
)
draw.ellipse(
(node_d.x - 5, node_d.y - 5, node_d.x + 5, node_d.y + 5),
fill=(128, 128, 0),
outline=(0, 0, 0)
)
draw.ellipse(
(node_e.x - 5, node_e.y - 5, node_e.x + 5, node_e.y + 5),
fill=(0, 128, 128),
outline=(0, 0, 0)
)
draw.ellipse(
(node_f.x - 5, node_f.y - 5, node_f.x + 5, node_f.y + 5),
fill=(128, 0, 128),
outline=(0, 0, 0)
)
im.save(f'image-{n:04d}.png')
process_vector(node_a, node_b, coef, False)
process_vector(node_a, node_c, coef, False)
process_vector(node_a, node_d, coef, True)
process_vector(node_a, node_e, coef, True)
process_vector(node_a, node_f, coef, True)
process_vector(node_b, node_c, coef, False)
process_vector(node_b, node_d, coef, True)
process_vector(node_b, node_e, coef, False)
process_vector(node_b, node_f, coef, False)
process_vector(node_c, node_d, coef, True)
process_vector(node_c, node_e, coef, False)
process_vector(node_c, node_f, coef, False)
process_vector(node_d, node_e, coef, False)
process_vector(node_d, node_f, coef, False)
process_vector(node_e, node_f, coef, False)
node_a.process_position()
node_b.process_position()
node_c.process_position()
node_d.process_position()
node_e.process_position()
node_f.process_position()
Initial position
Position after 10 steps.
As mentioned before, this method is great to adjust the position when the nodes are already in their approximate position. But you might want to adjust the formula used to compute both the attraction and the repulsion.
That’s all folks!