創建DAG表格表示的算法？

給定一個DAG，其中每個節點屬於一個類別，該圖表如何轉換爲每個類別都有列的表格？這種轉換不一定是可逆的，但應該保留關於圖的結構的有用信息;並且應該是一種「自然」轉換，因爲看着圖表和表格的人不應該對任何行感到驚訝。它也應該是緊湊的，即具有幾排。創建DAG表格表示的算法？

例如，給定具有邊a1-> b1，a1-> b2，b1-> c1，b2-> c1（即菱形圖）的節點a1，b1，b2，c1的圖表，我期望看看下錶：

a b c 
-------- 
a1 b1 c1 
a1 b2 c1

我已經想過這個問題相當多，但我有想出一種算法，給出了一定的圖表直觀結果麻煩。考慮具有邊a1-> c1，b1-> c1的圖a1，b1，c1。我想算法產生這種表：

a b c 
-------- 
a1 b1 c1

但也許它應該產生這個代替：

a b c 
-------- 
a1 c1 
a1 b1

我正在尋找創意和見解的問題。如果您認爲這會有所幫助，請隨意變更以簡化或限制問題。

頭腦風暴離開！

編輯：

改造應該總是產生相同的行集，但行的順序並不重要。

使用例如Excel進行排序和過濾時，表格應該表現得很好。這意味着多個節點不能被打包到表格的單個單元中 - 每個單元只有一個節點。

來源

2009-11-20 rattigan

這裏是我落得這樣做：

查找一個節點發出的所有路徑沒有入邊。（可能是一些圖便宜，但適用於礦山）
遍歷每個路徑收集值行
緊湊的行

壓實行是多內斯如下。

對於每對列×的，Y
- 構建地圖x到它的每一個值的的Y
- 創建另一個地圖有關條目僅具有Y的一個不同值的可能值，將x的值映射爲y的單值。
使用這些貼圖填充空白。填寫數值時，請檢查可填寫的相關空白。

這給出了非常緊湊的輸出，似乎滿足我所有的要求。

來源

2009-11-24 16:12:40 rattigan

如何將一個節點上的所有可到達節點壓縮在一個單元格中？例如，您的第一個DAG應該如下所示：

a b  c 
--------------- 
a1 [b1,b2] 
    b1  c1 
    b2  c1

來源

2009-11-20 20:24:23

這實際上並不是我在桌上所要找的。我想我認爲重要的是表格應該以關係的方式表現良好，因爲我希望能夠在列上進行排序，並使用過濾器進行過濾。自動過濾器在Excel中。這種表示不符合該目標。還是）感謝你的建議！ – rattigan 2009-11-20 20:33:50

您需要的是變體topological sorting。這是一種「排序」圖頂點的算法，就好像a---->b邊緣意思是a > b。由於圖形是一個DAG，因此它沒有周期，並且這種關係是可傳遞的，所以至少存在一個排序順序。

對於你的鑽石形圖中，兩個拓撲訂單存在：

a1 b1 b2 c1 
a1 b2 b1 c1

b1和b2項目不連接，即使是間接的，因此，它們可以被放置在任何順序。

對圖進行排序後，您知道訂單的近似值。我的建議是直接填寫表格（每行1個頂點），然後「緊湊」表格。執行排序並選擇您獲得的序列作爲輸出。填寫該表從上到下，分配頂點到相關列：

a b c 
-------- 
a1 
    b2 
    b1 
     c1

現在，通過從頂部走到底部壓實表（再作出類似的傳球從底部到頂部）。每次迭代時，仔細看一下「當前」行（標記爲=>）和「下一行」。

如果列在當前和下一個節點節點不同，什麼也不做此列：

 from  ---->  to 
    X b c   X b c 
    --------   -------- 
=> X1 . .   X1 . . 
    X2 . .  => X2 . .

如果在接下來的行中的列X沒有頂點（表單元格是空的），在當前行中有頂點X1，那麼你有時應該填充這個空單元格當前行中的一個頂點。但並非總是如此：你想讓你的桌子變得合乎邏輯，不是嗎？因此，複製頂點當且僅當沒有邊緣b--->X1,c--->X1等，爲當前行中的所有頂點。
```
 from  --->  to 
    X b c   X b c 
    --------   -------- 
=> X1 b c   X1 b c 
     b1 c1  => X1 b1 c1 
```

（編輯:)第一（前）和第二（落後）之後的推移，你就會有這樣的表：

first  second 
a b c  a b c 
-------- -------- 
a1   a1 b2 c1  
a1 b2  a1 b2 c1 
a1 b1  a1 b1 c1 
a1 b1 c1 a1 b1 c1

然後，就等於去掉行和你完成：

a b c 
-------- 
a1 b2 c1 
a1 b1 c1

，你應該得到一個不錯的表。爲O（n^2）。

來源

2009-11-20 20:38:25

這是一個有趣的方法。但是，我想知道它是否是確定性的 - 結果取決於您選擇哪種拓撲排序，至少對於更復雜的DAG？我不在乎同一組行是否會導致不同的順序，但我不會對可能導致不同行集的算法感到滿意。我將更新問題以反映這一要求。 – rattigan 2009-11-20 20:51:29

我試圖用邊a1-> b1，b1-> c1，c1-> d1，a1-> b2，b2-> c2，c2-> d1做DAG。我不確定我是否理解規則二，所以我無法做到。但重點是這個圖有拓撲排序，看起來好像他們可以產生不同的結果：a1，b1，c1，b2，c2，d1和a1，b1，b2，c1，c2，d1。你明白我的意思嗎？ – rattigan 2009-11-20 21:19:02

@rattigan，是的，它可以產生不同的結果。您可以執行更具體的處理來對記錄進行排序（例如，爲圖形添加更多邊緣），但它超出了我的答案範圍。至於規則二，我正在修改措辭讓你再試一次。 – 2009-11-20 22:09:01

這聽起來像是一個列車系統地圖，車站在區域內（a，b，c）。

您可能會在一個方向上生成所有可能路線的表格。在這種情況下，「a1，b1，c1」似乎意味着a1-> b1，所以如果你只有a1-> c1，b1-> c1，則不要這樣來格式化。你可以決定生成一個表格通過列出從區域a開始的最長路線，僅使用每個邊緣一次，以短的剩餘路線結束。或者只允許邊連接未使用的邊或擴展路線才能重複使用邊。

換句話說，先進行深度優先搜索，嘗試不重用邊（拒絕任何不包含未使用邊的路徑，並可選地修剪使用的邊在端點處）。

來源

2009-11-20 20:52:16

我喜歡這個想法。但是，生成的行集是否取決於表的遍歷順序？（請參閱編輯問題）也許這種變化也是一種選擇：形成所有可能路線的集合 - 排除其他路線的子路線 - 併爲每條路線發射一行。 – rattigan 2009-11-20 21:35:11

創建DAG表格表示的算法？

回答

相關問題