儘量減少網絡圖中的交叉線

我正在實現（考慮實際情況）一個控件，它允許用戶創建一系列節點中的Web圖。其目的是爲了創建一個「流程圖」，從一系列軟件的另一部分要求提出的問題中進行分類;對於每個問題，選擇的答案決定下一個問題。它有點FSMish，但比表格問題的線性進展要聰明得多。「如果你回答問題Y，請回答以下......」。該圖是一個網絡，並不能保證是一棵樹，因爲定義該圖的用戶可能想要問幾個後續問題，然後返回到「正常」問題線，因此兩個不同的節點可能會「合併」到同一個子節點。然而，網絡保證不是循環的並且有一個起點，因此通過圖的路徑數量有限，而且所有的路徑都是有限長的。儘量減少網絡圖中的交叉線

這是問題。我想要有一個「排列」按鈕（或者簡單地自動排列）來重新排列節點，以便連接網絡節點必須相互交叉的線條數量減到最少。大多數流程圖工具都有這個功能，但是我的Google-fu沒有找到這種通用算法。我已經將它定義爲「交叉數」問題，但似乎沒有找到具有V節點和E路徑的圖的最小交叉數的一般解決方案，並且任何這樣的解決方案都是NP-hard（if一個特定的子問題可以在一次操作中解決，那麼完整的問題可以在多項式時間內解決）。最重要的是，沒有任何參考文獻可以找到詳細的算法，可以用一個最小的（沒有任何「最小」）交叉數表示一個圖。

任何提示？

編輯：我給了Sharkos他出色的參考蜱。然而，假設圖有一個確定的起點，是單向的和非循環的，一個工作算法（可能不是最優）實際上很簡單。在僞代碼：

" 
Give all nodes an initial XScore, YScore and LinkScore of 0 
Determine the start node (either designated, or the one not linked to by any other) 
Set start node's XScore and YScore to 1 
Set running YScore = 1 
Start recursion 
for each path from node 
    if node on other end has XScore <= current  
     set other node's XScore to current + 1 
    if node on other end has YScore <= running YScore 
     set other node's YScore to running YScore 
     increment other node's LinkScore 
    Recurse with node on other end 
    Increment running YScore 

Order nodes by XScore, then YScore. 

--If the graph happens to be planar, we're done. 

--To minimize crossover: 

for each XScore 
    for each node with that XScore 
     if the next node with the same XScore has a higher LinkScore 
     swap the two nodes, exchanging YScores

來源

2012-08-09 KeithS

圖形繪製是一項棘手的業務，可能有成千上萬的出版物，對所有應用程序沒有明確的最佳解決方案。 [Graphviz dot]（http://www.graphviz.org/Documentation.php）通常在繪製圖表方面做得很好，但它沒有聲明任何最優性，並且有些情況下它完全不適合。你可以在子進程中運行'dot'並使用它的輸出，或者如果它的結果符合你的口味，就可以計算出它的效果。 – MvG 2012-08-09 19:35:03

這裏有一個關於這個話題，這給一些算法與討論Master's thesis，並給予很多很多不同的人的方法，從精確算法近似算法引用。然而，對於一種相當簡單，具體的僞代碼版本的「平面化方法」，顯然（不是專家，儘管我已經研究了圖論，而且聽起來似乎很有用），這是一種常見的近似方法，請參見this chapter中的第2.5節。 Handbook of Graph Drawing and Visualization，這是免費在線。

希望這是你想要的東西？

來源

2012-08-09 20:50:34 Sharkos

正是我想要的那種東西。 – KeithS 2012-08-09 20:52:20

儘量減少網絡圖中的交叉線

回答

相關問題