## 定义图

### 定义位置和力

```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);
}
}```

### 定义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)
}
}```

`connect` 方法用于构建图形时将节点连接到另外一个节点。 `hasEdge` 用于判断两个点是否连接。

### 定义构建树形图函数

```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;
}```

### 定义绘制的函数

```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();
}
}```

```class 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);
}```

`drawGraph(treeGraph(3, 5))`

## 力导向布局

```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));
}
}
}```

```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);
}```

runLayout函数里面主要做了两件事情: 1. 记录运行4000步所需要的时间 2.每运行100步绘制图形当前的布局。第一件事主要是为后面算法性能优化做一个参照。第二件事情, 主要是让我们能够大致感受到算法的推导过程。为了能够更加直观的感受到算法推导的变化过程, 我们增加节点的数量。

`runLayout(forceDirected_simple, treeGraph(4, 5))`

runLayout(forceDirected_simple, treeGraph(3, 5))

runLayout(forceDirected_simple, treeGraph(3, 5))

runLayout(forceDirected_simple, treeGraph(3, 5))

## 力导向算法的优化

`runLayout(forceDirected_simple, treeGraph(4, 5))`

### 避免做重复的工作

```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;
}
let applied =  apart.times(forceSize / distance);
node.pos = node.pos.plus(applied);
other.pos = other.pos.minus(applied);
}
}
}```

`runLayout(forceDirected_noRepeat, treeGraph(4, 5))`

### 牺牲一点点的布局效果, 提升算法效率

```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;
}
let applied =  apart.times(forceSize / distance);
node.pos = node.pos.plus(applied);
other.pos = other.pos.minus(applied);
}
}
}```

`runLayout(forceDirected_noRepeat_skip, treeGraph(4, 5))`

self time total time function
7.95ms 10.76ms forceDirected_noRepeat_skip
1.51ms 1.51ms hasEdge
0.53ms 0.53ms minus
0.49ms 0.49ms Minor GC

### 优化hasEdge函数

```hasEdge(other) {
return this.edges.includes(other)
}```

`hasEdge` 方法的变体添加到 `GraphNode` 类中。

```GraphNode.prototype.hasEdgeFast = function(other) {
for (let i = 0; i < this.edges.length; i++) {
if(this.edges[i] === other) return true
}
return false;
}```

```hasEdge(other) {
return this.hasEdgeFast(other)
}```

### 优化Minor GC

`Minor GC` 所花费的时间即为我们清理不再使用的内存所花的时间。在我们对树进行布局的过程中, 必然会产生很多临时的向量。虽然我们创建的一些向量会被引擎优化掉, 但是创建这些对象还是急需要一些成本的。为什幺避免创建对象的代码运行起来会更快呢? 主要是因为引擎必须找到一个存储对象的位置, 它必须弄清楚它们何时不再使用并回收他们, 当你访问它们的属性时, 它必须弄清楚他存储在内存中的位置。

```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;
let forceY = apartY * forceSize / distance;
node.pos.x  += forceX;
node.pos.y  += forceY;
other.pos.x -= forceX;
other.pos.y -= forceY;
}
}
}```

`runLayout(forceDirected_noRepeat_skip_noVector, treeGraph(4, 5));`