有向无环图的差分

Question

我正在寻找一种可以使用diff两个有向无环图(DAG)的算法.也就是说,我想要一种算法,它在第一个DAG上产生一系列删除和插入以产生第二个DAG.

我不是百分百肯定,但我认为最长的共同子序列可以应用于DAG.我不太关心结果编辑序列的长度(只要它足够短)并且更关心算法的运行时间.

一个复杂因素是除了单根节点外,我的顶点都没有被标记.根节点也是唯一具有零边的节点.标记了图形的边缘,图形中的"数据"由从根到叶的路径表示.这与a类似,trie但使用有向图而不是树.实际上我的图表与directed acyclic word graph数据结构非常相似.

这是一个例子.

DAG1

DAG2

要获得DAG 2,只需将根目录中的顶点添加到标签为"b"的另一个顶点即可.从该顶点开始,DAG 1中的最终"ac"顶点有一条边,而标签为"d"的新顶点有一条边.从最后一个顶点到DAG 1中的'ac'顶点还有另一条边.我会以DAG形式发布一个指向diff的链接,但我不能发布两个以上的链接.

谢谢,希望这足够清晰.

Answer 1

这可能有点太晚了但只是为了好玩:两个DAG都可以表示为矩阵,行索引表示"从"顶点,列索引表示"到"顶点,相应的单元格用边缘标记ID.您可以为顶点提供唯一且随机的ID.

下一部分有点棘手,因为只有你的边具有从DAG1映射到DAG2的有意义的标签.假设你有一组边缘E*是DAG1和DAG2标记边缘的交叉点,你需要执行一系列行移位(向上或向下移动)或列移位(向左或向右移动)所以所有位置DAG1和DAG2中E*中的边缘相互映射.请注意,对于Matrix中表示的DAG,整行或整列的移位位置仍然使表示等效.

剩下的操作是根据映射的矩阵重命名顶点,比较两个矩阵,并识别新的边和所需的新顶点(以及可以移除的边和顶点).