preface
Finding a beautiful layout for a given diagram is a well-known problem. There is no known solution to reliably find a beautiful layout for arbitrary graphs, especially for large graphs that correspond to dense connections. But for certain types of graphs, for example, floor plans (which can be drawn without intersecting each other), there are effective layout methods. During the drawing process, we need to pay attention to two points: 1. Performance 2. Visual effect. In short, how to build a beautiful image quickly. This paper will use the method of force oriented graph layout to complete the layout of nodes, and the final presentation results are as follows:
Define the figure
We can represent the layout of the graph as an array of GraphNode objects, each with its current position and an array of nodes corresponding to the changes it is connected to. We randomize their starting positions.
Define position and force
class Vec {
constructor(x, y) {
this.x = x;
this.y = y;
}
plus(other) {
return new Vec(this.x + other.x, this.y + other.y);
}
minus(other) {
return new Vec(this.x - other.x, this.y - other.y);
}
times(factor) {
return new Vec(this.x * factor, this.y * factor);
}
get length() {
return Math.sqrt(this.x * this.x + this.y * this.y); }}Copy the codeDefine GraphNode
class GraphNode {
constructor() {
this.pos = new Vec(Math.random() * 1000.Math.random() * 1000);
this.edges = [];
}
connect(other) {
this.edges.push(other);
other.edges.push(this);
}
hasEdge(other) {
return this.edges.includes(other)
}
}
Copy the codeThe connect method is used to connect a node to another node when building a graph. HasEdge is used to determine whether two points are connected.
Defines the build tree function
function treeGraph(depth, branches) {
let graph = [new GraphNode()];
if (depth > 1) {
for (let index = 0; index < branches; index++) {
let subGraph = treeGraph(depth - 1, branches);
graph[0].connect(subGraph[0]); graph = graph.concat(subGraph); }}return graph;
}
Copy the codeWhy use a tree diagram? The tree diagram contains no loops, which makes layout easier. It requires two parameters: 1. Depth Depth of the tree 2. Branches Branch tree to be created each time it is split. We recursively construct a tree structure with a given shape.
Define the function to draw
Now that all the work is done to create the tree diagram, you need to display the nodes of those diagrams on the canvas. So define a drawGraph function to draw the graph onto the canvas.
function drawGraph(graph) {
let canvas = document.querySelector("canvas");
if(! canvas) { canvas =document.body.appendChild(document.createElement("canvas"));
canvas.width = canvas.height = 500;
}
let cx = canvas.getContext("2d");
cx.clearRect(0.0, canvas.width, canvas.height);
let scale = new Scale(graph, canvas.width, canvas.height);
cx.strokeStyle = "#99CC99";
cx.lineWidth = 3;
for (let i = 0; i < graph.length; i++) {
let origin = graph[i];
for (let target of origin.edges) {
if (graph.indexOf(target) <= i) continue;
cx.beginPath();
cx.moveTo(scale.x(origin.pos.x), scale.y(origin.pos.y));
cx.lineTo(scale.x(target.pos.x), scale.y(target.pos.y));
cx.stroke();
}
}
cx.fillStyle = "#FF6666";
for (let node of graph) {
cx.beginPath();
cx.arc(scale.x(node.pos.x), scale.y(node.pos.y), nodeSize, 0.7); cx.fill(); }}Copy the codeclass Scale {
constructor(graph, width, height) {
let xs = graph.map(node= > node.pos.x);
let ys = graph.map(node= > node.pos.y);
let minX = Math.min(... xs);let minY = Math.min(... ys);let maxX = Math.max(... xs);let maxY = Math.max(... ys);this.offsetX = minX;
this.offsetY = minY;
this.scaleX = (width - 2 * nodeSize) / (maxX - minX);
this.scaleY = (height - 2 * nodeSize) / (maxY - minY);
}
Copy the codeI won’t bother with this part of the code drawn to the canvas, which is not the focus of this article. I’m sure most of you can understand that. Let’s create a tree with a depth of 3 and create 5 branches per split.
drawGraph(treeGraph(3.5))
Copy the codeThe following information is displayed:
Although the graph is displayed, it is clearly a poor visual experience, with dots and lines in a haphazard position. So our next priority is to make the layout of the diagram beautiful.
Force oriented layout
Before we begin with force-oriented layout, we need to understand what a force-oriented algorithm is. Here is an explanation of the force-oriented algorithm on Baidu Baike:
The force – oriented algorithm is a graph layout algorithm. Generally speaking, force-oriented algorithms include the following steps: mechanical modeling of network data, and obtaining a stable layout through a certain amount of time simulation. Force-guided algorithm is a commonly used method for data mapping of general mesh structures. Through the calculation of each node, the resultant force of gravity and repulsion is calculated, and then the resultant force moves the position of the node.
In addition, we need to pay attention to the fact that if the number of nodes is too large, the force-oriented algorithm cannot obtain satisfactory results. Therefore, the number of nodes in this paper is several hundred. With tens of thousands of nodes, the result is not as good as it should be.
With that in mind, it’s a little easier to understand the following layout algorithm. We will move the node one at a time, calculate the forces acting on the current node, and move the node in the direction of the combined forces of these forces. In middle school, we all learned that under ideal conditions, the force exerted by a spring can be approximated by Hooke’s Law, which states that the force exerted by a spring is proportional to the difference between the spring’s rest length and its current length.
Namely: delta F = k. Δ x.
So we define the springLength as 40, the rest length of the spring. Define springStrength as 0.1 as the elastic coefficient. If our current length is 50, then the spring force is (50-40) * 0.1 = 1; To prevent nodes from being directly too close or too far apart. We simulate each node as charged particles and use the repulsive force between them to achieve a relatively reasonable layout. Therefore, we use coulomb’s law derivation formula to complete the derivation of different node positions. An explanation of Coulomb’s law is as follows:
The force acting on two stationary point charges in the air is proportional to the product of their charges (q1Q2) and inversely proportional to the power of their distance (r^2). The direction of the force is along their line. The same charges repel each other, while the other charges attract
Corresponding to our scene, first of all, all the nodes in our graph are electrons at the same pole. If the two nodes are very close to each other, the square generated by them will be very small, and the force generated will become very large. As the distance between nodes increases, the repulsive force gradually decreases.
Namely: F = kQ1. Q2 / r squared
Similarly, we define Coulomb constant k as 1500. Const repulsionStrength = 1500.
Based on the above basic knowledge, I can form a simple derivation idea:
The force acting on a given node is calculated by circulating all the other nodes and applying repulsive forces to each of them. When another node shares an edge with the current node, a force caused by the spring is also applied. The following is the derivation algorithm based on Hooke’s Law and Coulomb’s Law generation:
const springLength = 40;
const springStrength = 0.1;
const repulsionStrength = 1500;
function forceDirected_simple(graph) {
for (let node of graph) {
for (let other of graph) {
if (other === node) continue;
let apart = other.pos.minus(node.pos);
let distance = Math.max(1, apart.length);
let forceSize = -repulsionStrength / (distance * distance);
if (node.hasEdge(other)) {
forceSize += (distance - springLength) * springStrength;
}
let normalized = apart.times(1/ distance); node.pos = node.pos.plus(normalized.times(forceSize)); }}}Copy the codeIn our scenario, both forces depend on the distance between the two points. For each pair of nodes, our function computes a vector called apart that represents the path from the current node to the other node, and then this function gets the actual distance by taking the length of the vector. In order to prevent the infinite force from being generated when the distance between nodes is infinitely close to 0, we uniformly set the distance less than 1 as 1. Based on the distance between the nodes, we calculate the force between the two nodes. We transform the scalar value into a vector, so we need to multiply the scalar value by the normalized version of the apart vector.
We define a function to test the implementation of our force-oriented algorithm:
function runLayout(implementation, graph) {
function run(steps, time) {
let startTime = Date.now();
for (let i = 0; i < 100; i++) {
implementation(graph);
}
time += Date.now() - startTime;
drawGraph(graph);
if (steps === 0) console.log(time);
else requestAnimationFrame(() = > run(steps - 50, time))
}
run(4000.0);
}
Copy the codeThe runLayout function does two main things: 1. Records the time it takes to run 4000 steps 2. Draw the current layout of the graph every 100 moves. The first thing is mainly to make a reference for algorithm performance optimization. The second thing, mainly, is to give us a sense of how the algorithm works. In order to feel the change process of algorithm derivation more intuitively, we increased the number of nodes.
runLayout(forceDirected_simple, treeGraph(4.5))
Copy the codeExecuting the code above gives us the following result:
What we found was that the dots, which were messy, became a lot nicer. In order to test the accuracy of the algorithm, we simulate trees in a variety of cases:
- runLayout(forceDirected_simple, treeGraph(3, 5))
- runLayout(forceDirected_simple, treeGraph(2, 5))
- runLayout(forceDirected_simple, treeGraph(3, 4))
Those of you who are interested can try other cases, and we can conclude that this algorithm can still meet the requirements for appearance. Then performance is often important in real business. The performance of the algorithm determines how long it takes to get the result the customer wants (figure).
Optimization of force steering algorithm
runLayout(forceDirected_simple, treeGraph(4.5))
Copy the codeAfter executing the code above, we opened the Browser console and found that it performed 4000 iterations in the range of 8500ms to 9000ms. That seems a little long, but let’s see if we can do better.
Avoid reinventing the wheel
The quickest way to do something is to avoid doing it altogether, or at least part of it. In our algorithm, the force between each pair of nodes is calculated twice, once when the first node is moved and once when the second node is moved. Since the forces act on each other, there is no need to calculate twice.
So we need to change the inner loop to only traverse the nodes after the current node, so that each pair of nodes is evaluated only once. The specific algorithm derivation process is as follows:
function forceDirected_noRepeat(graph) {
for (let i = 0; i < graph.length; i++) {
let node = graph[i];
for (let j = i + 1; j < graph.length; j++) {
let other = graph[j];
let apart = other.pos.minus(node.pos);
let distance = Math.max(1, apart.length);
let forceSize = -repulsionStrength / (distance * distance);
if (node.hasEdge(other)) {
forceSize += (distance - springLength) * springStrength;
}
letapplied = apart.times(forceSize / distance); node.pos = node.pos.plus(applied); other.pos = other.pos.minus(applied); }}}Copy the codeWe re-execute:
runLayout(forceDirected_noRepeat, treeGraph(4.5))
Copy the codeAfter testing, it is found that the time is only 6300ms, about 30% faster than before. If you are interested, you can test it on other browsers. You will find that different browsers speed up differently, depending on the browser engine.
Sacrifice a little bit of layout effect to improve algorithm efficiency
When the distance between two nodes is large, the effect of repulsion between them on the layout effect is negligible. So we just need to set a proper distance, ignore the proper force can also achieve a good layout.
Let’s define the distance as 175.
Based on the above ideas, we continue to optimize the code:
const skipDistance = 175;
function forceDirected_noRepeat_skip(graph) {
for (let i = 0; i < graph.length; i++) {
let node = graph[i];
for (let j = i + 1; j < graph.length; j++) {
let other = graph[j];
let apart = other.pos.minus(node.pos);
let distance = Math.max(1, apart.length);
let hasEdge = node.hasEdge(other);
if(! hasEdge && distance > skipDistance)continue;
let forceSize = -repulsionStrength / (distance * distance);
if (node.hasEdge(other)) {
forceSize += (distance - springLength) * springStrength;
}
letapplied = apart.times(forceSize / distance); node.pos = node.pos.plus(applied); other.pos = other.pos.minus(applied); }}}Copy the codeWe re-execute:
runLayout(forceDirected_noRepeat_skip, treeGraph(4.5))
Copy the codeAfter the test, it only takes about 2700ms. It’s clear we’re at least 50% faster. The above two optimization items are our reasoning to the program, to achieve a macro optimization results. But when the program performs micro-optimization, we can’t rely on the reasoning of the program, we need to analyze the points that can be optimized through micro-level observations. Micro-level observations can be obtained through the browser’s built-in Performance.
Let’s make a table for each subtask in red:
| self time | total time | function |
|---|---|---|
| 7.95 ms | 10.76 ms | forceDirected_noRepeat_skip |
| 1.51 ms | 1.51 ms | hasEdge |
| 0.53 ms | 0.53 ms | minus |
| 0.49 ms | 0.49 ms | Minor GC |
Optimize the hasEdge function
This is the hasEdge method
hasEdge(other) {
return this.edges.includes(other)
}
Copy the codeAdd a variant of the hasEdge method to the GraphNode class.
GraphNode.prototype.hasEdgeFast = function(other) {
for (let i = 0; i < this.edges.length; i++) {
if(this.edges[i] === other) return true
}
return false;
}
Copy the codeInstead of calling the includes method, we’ll call the variation on the GraphNode prototype.
hasEdge(other) {
return this.hasEdgeFast(other)
}
Copy the codeRe-running the code found that the time was about 600ms faster.
Optimization of Minor GC
The time taken by the Minor GC is the time it takes us to clean up memory that is no longer in use. As we lay out the tree, there are bound to be many temporary vectors. Although some of the vectors we create will be optimized by the engine, creating these objects will cost a lot of money. Why does code that avoids creating objects run faster? Mainly because the engine has to find a place to store objects, it has to figure out when they are no longer used and reclaim them, and when you access their properties, it has to figure out where they are stored in memory.
function forceDirected_noRepeat_skip_noVector(graph) {
for (let i = 0; i < graph.length; i++) {
let node = graph[i];
for (let j = i + 1; j < graph.length; j++) {
let other = graph[j];
let apartX = other.pos.x - node.pos.x;
let apartY = other.pos.y - node.pos.y;
let distance = Math.max(1.Math.sqrt(apartX*apartX + apartY*apartY))
let hasEdge = node.hasEdge(other);
if(! hasEdge && distance > skipDistance)continue;
let forceSize = -repulsionStrength / (distance * distance);
if (node.hasEdge(other)) {
forceSize += (distance - springLength) * springStrength;
}
let forceX = apartX * forceSize / distance;
letforceY = apartY * forceSize / distance; node.pos.x += forceX; node.pos.y += forceY; other.pos.x -= forceX; other.pos.y -= forceY; }}}Copy the codeThe new code is much more verbose than the previous one. Let’s rerun:
runLayout(forceDirected_noRepeat_skip_noVector, treeGraph(4.5));
Copy the codeThe discovery time was reduced to 1700ms. 9000ms -> 1700ms is already a lot of room for improvement. But not all programs need to consider tuning the Minor GC. Only if you have a very large amount of data should you consider it, otherwise verbose code is not maintainable.
Below is the final optimized effect picture:
At the end
After running the final code, we found the shape and performance of the diagram to be satisfactory. Of course, if you are interested, you can try to optimize it further. The specific algorithm code of this paper can be obtained from my Github, and interested students can run the code to experience the algorithm derivation process.
The resources
- eloquent javascript
- Hooke’s law
- Coulomb’s law