定向非循環圖的差異

Question

我正在尋找一種算法，它可以有兩個定向非循環圖（DAG）。也就是說，我想要一個在第一個DAG上產生一系列刪除和插入的算法來生成第二個DAG。

我並不百分百確定，但我認爲最長的公共子序列可以應用於DAG。我不太關心編輯序列的長度（只要它足夠短），並且更關心算法的運行時間。

一個複雜因素是我的頂點沒有標記，除了單個根節點。根節點也是邊緣爲零的唯一節點。圖的邊被標記，圖中的'數據'由從根到葉的路徑表示。這與trie類似，但使用有向圖而不是樹。實際上，我的圖形與directed acyclic word graph數據結構非常相似。

下面是一個例子。

DAG1

DAG2

要獲得DAG 2，您只需從根本上增加一個頂點到另一個頂點標籤爲 'B'。從該頂點到DAG 1中的最後'ac'頂點有一個邊，並且有一個邊到達標號爲'd'的新頂點。從最後一個頂點到DAG 1中的'ac'頂點有另一條邊。我會在DAG表單中發佈一個指向diff的鏈接，但我不能發佈兩個以上的鏈接。

感謝並希望這足夠清晰。

Answer 1

這可能有點晚，但只是爲了好玩： 您的DAG都可以表示爲矩陣，行索引表示「from」頂點，列索引表示「to」頂點，而用edge id標記的相應單元格。你可以給頂點唯一的和隨機的ID。

下一部分有點棘手，因爲只有你的邊緣有從DAG1到DAG2的有意義的標籤。假設您有一組邊E *，它們是來自DAG1和DAG2的標記邊的相交點，則需要執行一系列行移位（向上移動或向下移動）或列移位（向左移動或向右移動），以使所有位置DAG1和DAG2中的E *邊緣相互映射。請注意，對於在Matrix中表示的DAG，移動整行或整列的位置仍然使該表示等同。

其餘操作將根據所映射的矩陣來重命名頂點，比較兩個矩陣，並確定可以去除所需要的新的邊緣和新的頂點（和邊和頂點。