小编Nom*_*010的帖子

我正在寻找一种可以使用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的链接,但我不能发布两个以上的链接.

谢谢,希望这足够清晰.