Warning: stream_socket_client(): php_network_getaddresses: getaddrinfo failed: System error in /home/mathieu/www/rodic-wp/wordpress-20160713/wp-includes/class-wp-http-streams.php on line 150

Warning: stream_socket_client(): unable to connect to ssl://rodic.fr:443 (php_network_getaddresses: getaddrinfo failed: System error) in /home/mathieu/www/rodic-wp/wordpress-20160713/wp-includes/class-wp-http-streams.php on line 150
Weighted graphs: generate a layout in C++ – Mathieu Rodic

# Weighted graphs: generate a layout in C++

### 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&lt;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 &quot;area&quot; 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.

Warning: Unknown: open(/var/lib/php5/sessions/sess_14db6m5o5up1nfi86buq0qd4i4, O_RDWR) failed: Permission denied (13) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5/sessions) in Unknown on line 0