描述

本文簡要介紹力導向算法的原理，提供了源碼和D3繪制的實驗結(jié)果圖。

Force-Directed Layout algorithms are graph drawing algorithms based only on information contained within the structure of the graph itself rather than relying on contextual information.

力導向布局算法是一類繪圖算法，它僅僅基于圖的解構(gòu)本身來繪圖，而不依賴于上下文信息。

力導向繪圖 (Force-directed graph drawing)可以用于描述關(guān)系圖的結(jié)點之間的關(guān)系，把結(jié)點分布到畫布上合理的位置，比如描述企業(yè)之間的關(guān)系，社交網(wǎng)絡(luò)中的人際關(guān)系等。

原理

斥力(Repulsive Force)

把每個節(jié)點看做一個電荷，電荷與電荷之間存在斥力，也就是庫侖力，根據(jù)庫侖定律( Coulomb's law)，電子之間的斥力可以這么計算：

Coulomb's law

假設(shè)每個電子的電量都是1，那就有:

F = k/r².

常數(shù)k可以根據(jù)畫布大小和電子數(shù)量計算。
由于需要更新x,y坐標，可以分別計算斥力產(chǎn)生的正向位移。

displacementX =  distX / dist * k * k / dist * ejectFactor

*關(guān)于計算x, y偏移和常數(shù)k的方式，可能并沒有特別明確的方式，這里可能并不是最優(yōu)的方法。

引力(Traction Force)

一些粒子之間被一些邊所牽連，這些邊產(chǎn)生類似彈簧的胡克引力：

Fs=ks(x?x0)

牽制著邊兩端的粒子。斥力和引力不斷作用，粒子在不斷位移之后趨于平衡，逐漸不再發(fā)生相對位移，能量不斷消耗，最終趨于零。

在引力和斥力地作用下不斷地更新坐標，經(jīng)過多次迭代達到一個穩(wěn)定狀態(tài)，收斂結(jié)束。參數(shù)和迭代次數(shù)需要調(diào)試。

我分別用Java和JavaScript簡單實現(xiàn)了這個算法，并且利用D3做圖形化展示，下面是一些跑出來的數(shù)據(jù)呈現(xiàn)出的分布圖：

用Java和JavaScript簡單實現(xiàn)了這個算法，一些數(shù)據(jù)分布如下：

Graph 1. Iteration simulation of 24 nodes.

Graph 2. Randomly generated 20 nodes, each having 1~7 links.

Graph 3. Simulation of 100 nodes, iterating for 200 times.

代碼

代碼在我的Github上。

Refs:
https://www.ibm.com/developerworks/cn/web/0909_fudl_flashsocial/#major3
https://blog.csdn.net/newworld123made/article/details/51443603
http://philogb.github.io/blog/2009/09/30/force-directed-layouts/
https://bl.ocks.org/mbostock/4557698