「堆疊」與「懸掛」分層圖形繪製算法的標準名稱？

以下是繪製相同層次結構的兩種不同方法。請注意，在「堆疊」佈局中，節點總是比其最高「子」節點高一層。（重要：再如看到問題的底部編輯）「堆疊」與「懸掛」分層圖形繪製算法的標準名稱？

做這兩種類型的分層繪製方法有特定的名稱？我試圖找到現有的「堆疊」算法，但似乎無法顯示任何信息，因爲我不知道它叫什麼。

如果他們沒有名稱來區分它們，因爲它們依賴於相同的算法，是否有衆所周知的參數集用於通過現有算法獲得圖的「堆疊」版本？謝謝！

編輯：雖然上面的圖是嚴格的「trees」，我正在尋找算法應該能夠處理這種情況的節點有一個以上的家長那裏是從根本多個路徑的情況下，和案件葉子。 Here's an example和here's another。

編輯2：如果對任何人都有用，使用預先計算的節點圖層（y軸約束）的哈克（緩慢）力指向方法似乎可以正常工作。 Here's what it looks like。這個例子使用cytoscape.js和cola.js，它是顛倒的。這不是一個解決這個問題的方法，所以我只是把它作爲一個編輯。

(SO wouldn't let me submit the JSBin link without a code block...)

來源

2017-08-20 JoeRocc

如果我理解正確，左邊的每個節點的y位置取決於任何子節點的*最大*深度？那麼根據定義葉節點有y = 0？這基本上是你的算法。 – MSalters

是的，正好。兩者都有非常簡單的節點深度規則 - 它們之間有一些相反的地方，一個錨定葉節點，另一個錨定根節點。我想象最小化交叉的邏輯會有點不同，但我沒有想太多，因爲我希望/假設有一堆已經在我身邊使用的實現。 – JoeRocc

交叉？樹是一個平面圖。一定是，它是非循環的。因此，零交叉。簡單地說：任何有限樹都有每個節點的子節點上限N以及有限的深度D.因此，每棵樹都是深度爲D的完整N元樹的一個子集，在沒有交叉的情況下很容易繪製。 – MSalters

我不知道上述的任何具體名稱。看起來在兩種情況下分層算法都是最小化高度但基本上忽略寬度的longest path algorithm。如果您從底部開始對圖形進行分層，並且圖形有許多匯（頂出度爲零），那麼您將獲得寬底層（「堆疊」佈局？）。如果您從上到下對圖進行分層，並且它有許多來源（零度入射的頂點），那麼您將獲得一個寬頂層（「懸掛」佈局？）。

來源

2017-08-30 11:00:43

「堆疊」與「懸掛」分層圖形繪製算法的標準名稱？

回答

相關問題