類似Graphviz的工具是如何實現自動排版的？

01-02

無論畫哪種圖,節點有多少個,節點之間關係如何,感覺Graphviz都能畫的很美觀,例如:

想知道它是如何實現這樣的自動排版的?

謝邀。節點圖的可視化有幾種主要的演算法：

分層繪圖模型（Layered graph drawing）：也就是題主給出的圖片所用的演算法。分層繪圖演算法的本質很簡單，就是算出每個節點在圖中的「階級」，然後按階級從上向下（或者其他方向也行）依次畫出各個節點以及連線。這個演算法最適合的圖的類型是有向無環圖（Directed Acyclic Graph，簡稱 DAG），因為這樣的圖可以輕易用「與根節點的最大距離」（米爾斯基定理 Mirsky"s theorem）等方法來分配層級。如果圖不是 DAG 的話，分層繪圖演算法會先通過某些 Heuristics（不要吐槽英文，這個真的不知道怎麼說）規則來發現並去掉一些違背 DAG 性質的連線，把原圖變成一個比較接近原圖的 DAG。分層繪圖適用於跟有向無環圖比較接近的節點圖，缺點是環一多就比較容易亂包，而且對於無向圖來說，找到適合繪圖的根節點也比較困難。例子：
力場繪圖模型（Force-directed graph drawing）：力場模型是這些年出來的數據可視化框架中比較受歡迎的一種演算法。力場演算法的本質就是給節點和連線之間、節點和節點之間賦予受力關係，然後對整個圖的勢能做最小化。最常見的力場模型是把節點模擬為帶相同電荷的帶電粒子（這樣節點和節點之間就有了斥力，不會擠在一起），把連線模擬為彈簧（這樣可以平衡節點間的距離）。當然力場繪圖還有很多其他模型，也不只有勢能最小化一種優化方法，但是鑒於這只是個簡介我就不詳述了。力場繪圖模型相對分層模型的好處是處理環比較多的節點圖，或者無向圖的時候效果很出色，缺點是節點一多，最小化勢能就非常困難。例子：
形狀為先的繪圖模型：事實上這個名字是我編出來的，可視化里並沒有這個術語。這裡說的主要有兩大類常見繪圖模型，中心繪圖和圓環繪圖。顧名思義，中心繪圖就是找到一個中心點，把其他所有節點都畫成從中心節點發散出來的射線，而圓環繪圖則是把所有的節點放在一個圓環上，連線都從圓環內部走。這兩種模型的共同點都是形狀為先，各只適用於某種特別的目的和特別的節點圖類型。例子：（上面是中心繪圖，下面是圓環繪圖）

（圓環圖引用的是 @蘇莉安畫的 @黃繼新與知乎前兩百大V關注關係圖，我覺得很合適，哈哈）

最後無恥地說一句，最近正在學習d3.js，可能會寫一篇關於可視化的專欄，歡迎關注最大偏離，最小方差 - 知乎專欄

Graphviz 有學術文獻，如[1]。

如果要為這種演算法歸類的話，應該是屬於最優化演算法。給定一些約束（如節點間的最小距離），以及目標函數（如總邊線距離最短等），找出最優解（如節點的位置）。

[1] Ellson, John, et al. "Graphviz and dynagraph—static and dynamic graph drawing tools." Graph drawing software. Springer Berlin Heidelberg, 2004. 127-148. http://www.researchgate.net/profile/Emden_Gansner/publication/216633938_Graphviz_and_Dynagraph_--_Static_and_Dynamic_Graph_Drawing_Tools/links/0fcfd5107f9a6280ef000000.pdf

《Graph Drawing by High-Dimensional Embedding》

http://www.emis.de/journals/JGAA/accepted/2004/HarelKoren2004.8.2.pdf

知道一個力場繪圖模型，來自這本書最後一章節優化部分，線上有代碼，不多。

Eloquent JavaScript :: Code Sandbox