### What is this all about?

Graphs are becoming more and more popular to represent interconnected data. We’ll see here how to make a simple program taking the weights of the relations between the nodes as an input, and outputs the coordinates of the nodes as an output.

For example, imagine we have in a graph containing 4 nodes, linked as follows:

Index of the first node | Index of the second node | Weight of the link |
---|---|---|

0 | 1 | 1.0 |

1 | 2 | 1.0 |

2 | 0 | 1.0 |

2 | 3 | 1.0 |

From this list of edges, we want to calculate the 2D coordinates for each of the nodes.

### How do we compute the layout?

Fruchterman and Reingold published an article evoking a very efficient method for creating graph layouts. I adapted their algorithm to make it work with weighted graphs, as the original method was only designed for unweighted graphs.

### The code

The `GraphLayoutNode`

structure represents a node, with its position and displacement. The displacement is how much the node will moved during the current step.

struct GraphLayoutNode { struct { float x; float y; } position; struct { float x; float y; } displacement; }; |

The `GraphLayoutEdge`

structure represents an edge. It contains a reference to each of the two nodes that are being linked, and the weight of the link.

struct GraphLayoutEdge { GraphLayoutNode &node1; GraphLayoutNode &node2; float weight; }; |

The `GraphLayout`

structure will contain the full graph, a.k.a its edges and nodes. It also has two methods: adding a link (edge), and a method to compute the 2D coordinates.

`addLink()`

adds a link between two nodes`compute()`

calculates the 2D coordinates

struct GraphLayout { void addLink(size_t firstNodeIndex, size_t secondNodeIndex, float weight=1.f); void compute(size_t iterations); vector<GraphLayoutNode> nodes; vector<GraphLayoutEdge> edges; }; |

Let's have a look at the first method:

void GraphLayout::addLink(size_t index1, size_t index2, float weight) { // If the two indices are the same, or if the weight is zero, do nothing (no link) if (index1 == index2 || weight == 0.f) { return; } // If the number of nodes is lesser than one of the indices, extend the nodes vector size_t maxIndex = max(index1, index2); size_t nodesMaxIndex = nodes.size() - 1; for (size_t i=nodesMaxIndex; i<maxIndex; i++){ GraphLayoutNode node; nodes.push_back(node); } // Add an edge edges.push_back( (GraphLayoutEdge) { .node1 = nodes[index1], .node2 = nodes[index2] .weight = weight }); } |

Now, let's have a look at the algorithm itself, i.e. the compute() method:

void GraphLayout::compute(size_t iterations) { float nodesCount = nodes.size(); // Initialize nodes positions on a circle float a = 0.f; float da = 2.f * M_PI / nodesCount; for (auto node=nodes.begin(); node!=nodes.end(); node++) { node->position.x = nodesCount * cos(a); node->position.y = nodesCount * sin(a); a += da; } // Initial parameters; other values can be chosen for "area" float area = nodesCount; float k2 = area / nodesCount; float k = sqrt(k2); for (size_t i=0; i<iterations; i++) { // Temperature cools down; starts at 1, ends at 0 // (other formulas can be used for the cooling) float temperature = 1.f - i / (float)iterations; temperature *= temperature; // Calculate repulsive forces for (auto node1=nodes.begin(); node1!=nodes.end(); node1++) { node1->displacement = {0.f, 0.f}; for (auto node2=nodes.begin(); node2!=nodes.end(); node2++) { float dx = node1->position.x - node2->position.x; float dy = node1->position.y - node2->position.y; if (dx && dy) { float d2 = dx*dx + dy*dy; float coefficient = k2 / d2; node1->displacement.x += coefficient * dx; node1->displacement.y += coefficient * dy; } } } // Calculate attractive forces for (auto edge=edges.begin(); edge!=edges.end(); edge++) { float dx = edge->node1.position.x - edge->node2.position.x; float dy = edge->node1.position.y - edge->node2.position.y; float d2 = dx*dx + dy*dy; float coefficient = sqrt(d2) / k * edge->weight; edge->node1.displacement.x -= dx * coefficient; edge->node1.displacement.y -= dy * coefficient; edge->node2.displacement.x += dx * coefficient; edge->node2.displacement.y += dy * coefficient; } // Calculate positions float sum = 0.f; for (auto node=nodes.begin(); node!=nodes.end(); node++) { float d2 = node->displacement.x*node->displacement.x + node->displacement.y*node->displacement.y; float d = sqrt(d2); if (d > temperature) { float coefficient = temperature / d; node->displacement.x *= coefficient; node->displacement.y *= coefficient; sum += temperature; } else { sum += d; } node->position.x += node->displacement.x; node->position.y += node->displacement.y; } } } |

Et voilĂ !

The algorithm could be optimized… I’ll keep that for another post.