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.

What is this all about?

How do we compute the layout?

The code

Leave a Comment Cancel reply