在資料可視化的過程中，繪制網絡拓撲圖是很重要的，它能清晰呈現一個複雜網絡的結構，節點的重要性和關系。比如下面幾張圖：
下面這張圖是我的軟體繪制的：
這些都有一個共同的問題，就是如何讓圖繪制的更加美觀？ 複雜的圖結構，已經沒法人工布局了。是以計算機自動布局，就成了一個有趣而重要的話題。我們将其稱為布點算法。
一個好的布點算法應該能盡量滿足以下四個特點：
對稱性：繪制網絡對應将具有相同結構的子圖圍繞繪圖中心平衡布局
連接配接角最大化原則，使同一節點任意兩條邊形成的角度盡量大
邊交叉數量最小原則（最重要）：繪圖時應盡量減少互相交叉邊的數量。
直線邊原則：邊盡量直線，避免曲線，同時線盡可能短。其中，盡量避免交叉是最重要的，然而，并不是所有的圖結構都能滿足這個要求。同時，在性能上，還應當滿足如下需求：
算法應當能處理盡可能複雜和龐大的圖，比如上萬甚至上百萬的節點
運算速度還要盡量快，使其能夠在短時間内完成操作
可互動性，當使用者調整了某一個點的位置，或改變了一些參數，算法是否能夠動态調節？
圖分為有向圖和無向圖，有權圖和無權圖。當圖有權時，權重反映了節點間的關系，通常值越大，節點關系越緊密。
二維矩陣 最簡單也最友善的表示方法，當網絡結構巨大時，存儲空間浪費是驚人的，而且如果圖是無向圖，則矩陣是對稱的。但存取效率最高
臨接表， 即将邊表達為一個數組，<code>(x,y,dist) *n</code> 對于稀疏圖來說，存儲效率很高，但讀寫效率低。一種簡單的優化方法是對x和y 分别進行排序，排序後按二分查找，即可實作快速存取。
實時計算 當網絡圖巨大，而計算關系本身的運算并不複雜時，可以采用，此時dist[x][y] 被轉換為一個函數 getdistance(x,y), 實時完成計算。這是一種很有趣且比較實用的方法，尤其是當網絡圖稀疏時。
為了簡化，我們采用二維矩陣作為存取結構，相信讀者可以很容易的将其改寫為其他形式。
力導引布局的方法可以産生相當優美的網絡布局，并充分展現網絡的整體結構及其自同構特征。該方法最早由eades在1984年提出。
基本思想是将網絡看成一個頂點為鋼環，邊為彈簧的實體系統，系統被賦予某個初始狀态以後，彈簧彈力（引力和斥力）的作用會導緻鋼環移動，這種運動直到系統總能量減少到最小值停止。每次循環都要計算任意一對點的斥力和相鄰兩個點的引力，計算複雜度為o（n2）。
基本上絕大多數算法都遵循着這樣的原則，即：
将網絡看成一個頂點為鋼環，邊為彈簧的實體系統
不斷疊代，使整個系統的總能量達到最小
為了簡化，彈簧的受力并不遵循胡克定律，而是自己定義的受力公式，同時決定引力隻在相鄰節點間。是以，最基本的彈簧算法的僞代碼如下：
<code>随機分布g的節點 重複m次 { 計算作用在各個節點上的力 按照力移動節點的位置 } 根據節點位置繪圖</code>
衡量一個布點算法的美學标準，可以用下面幾個公式來計算：
其中:
最後:
fr算法改進了彈簧算法，是現在用途最為廣泛的布點算法，很多算法都是在這個算法上改進的。
fr受到了天體重力系統的啟發，使用力來計算每個節點的速度，而不是加速度，進而得到每個節點應當移動的距離。它的每次疊代分為三個步驟：
計算節點之間的排斥力
計算相鄰節點之間的吸引力
綜合吸引力和排斥力，通過最大位移限制移動的距離
kk算法使得能量最小化，在圖的布局上減少了邊的交叉，除了需要計算所有節點對之間的最短路徑，并不需要其他理論知識。它雖然每一步的計算複雜度高于fr算法，但疊代次數較少，使其執行速度和效果都比fr好。
上一部分是兩個月前寫的，今天發現了，想把剩下的補足。
本來想把之前的布點算法的代碼抽出來，做成一個獨立的工程，做成附件釋出出來，奈何之前學弟寫的代碼實在太亂亂亂了，我改了老半天，依然還有一大堆的問題，漸漸地我失去了耐心。覺得這篇文章要太監了。
說點感性的認識吧。布點算法很重要，因為能直覺的看出複雜網絡的結構和關系。但在點很多時，性能就得考慮，在時間上，幾百個點的計算幾乎瞬間即可完成，上萬個節點的圖，采用高性能的布點算法，在犧牲效果的情況下，能在兩分鐘内跑完，使用力導引算法，則要花費10分鐘以上。這可能和學弟實作的代碼不夠高效率有關系。
附錄給出了一個簡單的力導引實作，接口應該很容易，一看就能明白。
目前，推薦sm算法，相關連結：
<a href="https://en.wikipedia.org/wiki/stress_majorization">https://en.wikipedia.org/wiki/stress_majorization</a>
不過，不建議重複造輪子，有現成的graphviz可以使用。應該把時間花在更重要的事情上。如果我當時沒有對語言間互操作那麼反感，就不用耽擱那麼多功夫重寫c#版本了。
其實原本的代碼中，包含了sm,超大規模布點，力導引這三種算法的完整代碼，有需要的，可以站内我。如果你看到了這裡，說明你還是蠻有耐心的。