分層數據的最佳圖形繪製算法？

我已指示無環圖是近樹的集合，在下面的意義：每個圖都有一個根和頂點組織爲水平例如，如果v 和v 是頂點，然後如果v 水平小於v_{2水平，則存在從v到v_{1在圖中沒有}邊緣，儘管可能存在許多邊緣從v 到在相同或更高水平的頂點。例如，表達式樹，函數調用圖或線性類層次結構就是這樣的圖的例子。這裏是這樣的曲線圖的一個示例：}分層數據的最佳圖形繪製算法？

   A1    
      /\   A1 -> A4, A3 
      / \   A3 -> A2, A6, A7 
      A4 A2--A3  A2 -> A6 
       | \/\ 
       A6 \_ A7

有圖形的繪圖算法過多，我無法確定哪一個是最適合於這種情況。一些初步的研究表明，用於繪製Hasse圖的算法可能是合適的，但似乎這種算法的輸出不適用於我試圖建模的數據結構類型。還有幾種用於對分層數據進行建模的算法，但我不確定哪種算法能夠輕鬆實現效率。前一種方法存在的一個問題是這些圖形有一個根，也有一個方向。如果可能的話，該算法將支持循環圖，並儘量減少數值計算的次數，但這不是必需的。由於這些原因，我寧願避免強制執行算法，並且如果可能的話，可以使用GraphViz算法，如，點。

來源

2012-11-15 danportin

這不是一個真正的答案，但它太長了評論。

你的圖與一般的有向非循環圖有什麼不同？

DAG不一定要有根，但我認爲這對繪製圖形沒什麼影響。

就水平而言，對於任何DAG，都可以定義一個函數級別（v），使得對於任何邊沿，右邊; （i）≤等級（j），等級（i）≤等級（j）。平凡級函數是頂點的拓撲順序中頂點的索引。另一個是從根到頂點的最長路徑的長度。

Reingold-Tilford樹形圖繪製算法繪製有序樹（即樹頂點邊緣排序的樹）。你的例子表明你的圖不是有序的，事實上你面臨的主要問題是找到一個最小化邊交叉的邊緣排序。所以可能這是你正在尋求解決的問題。（這不是一個簡單的問題。）

dot事實上，在我的經驗中，DAG確實做得很好，雖然它有時需要一些幫助。特別是，如果您知道每個頂點的級別，則可以爲每個級別使用屬性「rank =」same「'創建一個子圖。（請參閱this example。）

來源

2012-11-15 06:50:32 rici

對於遲來的迴應我表示歉意;我沒有意識到還有一個額外的答案。我認爲你是正確的：除了邊緣交叉算法之外，使用樹形繪圖算法將是最好的選擇。這似乎是最好的答案，因爲它通過將樹形繪製算法與算法結合以最小化邊緣交叉來解決問題，從而澄清了問題。 – danportin

如果它完全是一棵樹，那麼我已經看到這個Reingold–Tilford Tree drawing algorithm以前工作得很好。順便說一下，我覺得允許節點A2'上升'到與其祖先相同的水平的決定並不是真的有很大的幫助。

相反，我會允許一個節點進一步下降，而不是上漲。這個例子可以畫得更好，如下所示在我看來。

  A1    
     /\   A1 -> A4, A3 
     / \   A3 -> A2, A6, A7 
     A4  A3   A2 -> A6 
      /| \ 
      A2 | A7 
      \ | 
      A6

這樣你甚至不需要標記邊緣方向。 [我誤解了你的原圖嗎？我認爲A2和A7之間沒有對嗎？]

來源

2012-11-15 01:47:47 Billiska

問題是圖形位於樹和完整非循環圖之間的某處。如果前者，我可以使用像你所建議的算法;如果是後者，我可以使用Sukiyama算法的線性時間優化或類似的方法。你說得對，允許一個節點「上升到」與祖先相同的水平可能沒有幫助;對於我正在使用的數據結構，這會導致按照您的建議對其進行轉換，但會限制可以繪製的圖表類。 – danportin

分層數據的最佳圖形繪製算法？

回答

相關問題