DAG是否有2D佈局算法，可以修正一個軸上的位置？

我有一個約3.300個頂點的DAG，可以通過dot作爲一個或多或少簡單的樹相當成功地佈局（事情變得複雜，因爲頂點可以有一個以上的前輩從一個完全不同的級別，所以交叉頻繁）。圖表中的每個頂點都是在原始過程中的特定時間生成的，我希望佈局中的一個軸表示時間：a -> v, b -> v等邊緣關係表示a和b在v之前的某個特定時間應運而生。DAG是否有2D佈局算法，可以修正一個軸上的位置？

是否有DAG的佈局算法，它允許我指定一個座標軸上的位置（或至少是距離），並在另一個座標軸上提供關於邊緣交叉點的最佳佈局？

來源

2016-09-22 user2722968

可以使DAG的topological sorting擁有的方式排序的頂點，每邊x->y，頂點x來比y之前。

因此，如果你有a -> v, b -> v，你會得到類似a, b, v或b, a, v。

使用這一點，你可以輕鬆地表示DAG就像這樣：

來源

2016-09-26 16:55:29

Hrms，我應該自己想到......雖然這種方法非常簡單並且易於實現：是否有實際證據證明對於任何DAG，邊緣交叉的結果都是最優的？ – user2722968

我已經找到了如何在'networkx'中進行拓撲排序，但實際上並不知道如何繪製拓撲排序順序，就像在答案中一樣。你能給我一些提示嗎？ –

如果我的理解是否正確，那麼你希望儘量減少你的圖形佈局邊緣的交叉數。如果是這樣，那麼答案是「否」，因爲這個問題在一般情況下被證明是NP完全的。見this，「交叉號碼是NP-Complete，Garey，Johnson」。

如果您需要一個不是最優但足夠好的解決方案，有多篇關於此主題的文章，因爲它與電路佈局密切相關。可能用谷歌搜索「穿越數字啓發式」並查看一些文章的摘要將更好地解決您的任務，然後我試圖盲目猜測您的需求。

來源

2016-09-30 18:18:37

是的，因爲@ Arturo-Menchaca說拓撲排序可能有助於減少重疊的邊數。但它可能不是最佳的。沒有好的邊緣交叉最小化算法。交叉最小化的問題是NP完全的。啓發式應用於解決這個問題。

這StackOverflow的鏈接可以幫助你：Drawing Directed Acyclic Graphs: Minimizing edge crossing?

我想你的問題是關係到圖形佈局的美觀的方法。文章Overview of algorithms for graph drawing,Force-Directed Drawing Algorithms中描述了一些啓發式方法。可能是有關平面圖或幾乎平面圖的信息也可以幫助你。

在維基頁面Planar graph,Crossing number (graph theory)中描述了用於檢查和繪製平面圖的算法的一些回顧。用於平面圖形繪製的庫和算法在StackOverflow問題How to check if a Graph is a Planar Graph or not?中描述。例如，文章GA for straight-line grid drawings of maximal planar graphs中的作者使用遺傳算法進行直線網格繪製。

關於幾乎平面圖的很好的描述在文章Straight-Line Drawability of a Planar Graph Plus an Edge,On the Crossing Number of Almost Planar Graphs中給出。

嘗試修改原始算法，使用您的條件與一個軸對齊。

來源

2016-09-30 20:52:09 Didgeridoo

DAG是否有2D佈局算法，可以修正一個軸上的位置？

回答

相關問題