（1）「繪圖與點圖形」

在Drawing graphs with dot，點的佈局算法描述如下：

點吸入四個主要階段的圖表。瞭解這一點有助於您瞭解點的佈局以及如何控制它們。點使用的佈局過程依賴於非循環圖。因此，第一步是通過顛倒某些循環邊的內部方向來打破輸入圖中出現的任何循環。下一步將節點分配給不連續的隊列或級別。在從上到下的繪圖中，等級確定Y座標。跨越多個等級的邊緣被分成「虛擬」節點和單位長度邊緣的鏈。第三步命令隊列中的節點避免交叉。第四步設置節點的X座標以保持邊緣短，最後一步路由邊緣樣條。基於Warfield [War77]，Carpano [Car80]和Sugiyama [STT81]的工作，這與大多數分層圖繪製程序一樣。我們建議讀者參考[GKNV93]爲點的算法進行徹底的解釋

該段引用的論文是這些：

[Car80] M. Carpano。自動顯示用於計算機輔助決策分析的分層圖。 IEEE Transactions on Software Engineering，SE-12（4）：538-546，1980年4月。（顯然可以購買here。）
Emden R. Gansner，Eleftherios Koutsofios，Stephen C. North，and Kiem-Phong Vo。一種繪製有向圖的技巧。 IEEE Trans。（可在Graphviz.org網站上獲得here）。
[STT81] K. Sugiyama，S.Tagwawa和M.Toda。，「軟件工程」，19（3）：214-230，1993年5月。可視化理解分層系統結構的方法。 IEEE Transactions on Systems，Man，and Cybernetics，SMC-11（2）：109-125，1981年2月（顯然可以購買here。）
[War77] John Warfield。交叉理論與層次映射。對系統，人與控制論，SMC-7 IEEE交易（7）：（顯然可以轉讓here）505-523，1977年7月

（2）「用於繪製有向圖技術」

dot的算法在1993年發表在期刊IEEE Transactions on Software Engineering（並可在Graphviz.org網站上免費獲得）的論文"A Technique for Drawing Directed Graphs"中有詳細描述。這是上面引用的「[GKNV93]」來源。

抽象的，對於它的價值，是這樣的：

我們描述了四遍算法繪製有向圖。第一遍使用網絡單純形算法找到最佳排名分配。第二遍通過迭代啓發式來設置排名內的頂點順序，所述迭代啓發式結合了新穎的權重函數和局部轉置來減少交叉。第三遍通過構建和排列輔助圖來找到節點的最佳座標。第四遍使樣條曲線繪製邊緣。該算法制作出優秀的圖紙，運行速度很快

（3）「使用的Graphviz作爲庫」

"Using Graphviz as a Library"提供每個佈局引擎的algorithim的3.1節中的摘要。點的描述部分是這樣的：

如果可能的話，點算法產生關於邊緣方向的圖的排名佈局。它特別適合顯示層次或有向無環圖。基本佈局方案歸屬於Sugiyama等人[STT81] dot使用的具體算法遵循Gansner等人描述的步驟[GKNV93]

點佈局中的步驟是：1）初始化2）秩3）mincross 4）position 5）sameports 6）splines 7）compoundEdges

初始化後，算法使用整數程序爲每個節點分配一個離散秩（rank），以最小化（離散）邊長的總和。下一步（mincross）重新排列隊列中的節點以減少邊緣交叉。接下來是實際座標到節點的分配（位置），使用另一個整數程序來壓縮圖形並拉直邊緣。此時，所有節點將在coord屬性中設置一個位置。另外，設置所有簇的邊界框bb屬性。

「[GKNV93]」的引用是上面鏈接的「A Technique for Drawing Directed Graphs」。

「[STT81]」的引用是上面引用的「用於分層系統結構的視覺理解的方法」。

（4）您可能也有興趣：

Graphviz's Documentation Index，其中有鏈接詳細的文檔和其他背景材料。
Graphviz's "Theory" page哪個鏈接到更多的背景材料。
The raw source code for dot，它在GitHub上可用。
關於d3.js Google Group的一些相關討論。

來源

2013-12-12 07:19:47 Rod

Nice compilation – RaphaelH

Graphviz點算法

回答

（1） 「繪圖與點圖形」

（2） 「用於繪製有向圖技術」

（3） 「使用的Graphviz作爲庫」

（4）您可能也有興趣：

相關問題

（1）「繪圖與點圖形」

（2）「用於繪製有向圖技術」

（3）「使用的Graphviz作爲庫」