我正在寻找一种可以对两个有向无环图(DAG)进行diff编码的算法。也就是说，我想要一种算法，该算法在第一个DAG上生成一系列删除和插入序列，以生成第二个DAG。
我不确定百分百，但我认为最长的常见子序列可以应用于DAG。我不太担心结果编辑序列的长度(只要足够短)，而更多地关注算法的运行时间。
一种复杂的情况是，除单个根节点外，没有其他任何顶点被标记。根节点也是唯一具有零边缘的节点。图的边缘被标记，图中的“数据”由从根到叶的路径表示。这类似于trie，但有向图而不是树。实际上，我的图非常类似于directed acyclic word graph数据结构。
这是一个例子。
DAG1
DAG2
要获取DAG 2，只需将一个顶点从根添加到另一个带有标签“b”的顶点。从该顶点开始，DAG 1中的最终“ac”顶点具有一个边缘，而标签为“d”的新顶点则具有一个边缘。从该最终顶点开始，DAG 1中的“ac”顶点有另一个边缘。我以DAG形式发布了到diff的链接，但我不能发布两个以上的链接。
谢谢，希望这足够清晰。
最佳答案
这可能为时已晚，但只是为了好玩:
您的两个DAG都可以表示为矩阵，其中行索引指示“起始”顶点，列索引指示“至”顶点，相应的单元格标记有Edge ID。您可以给顶点唯一和随机的ID。
下一部分有些棘手，因为只有边缘具有有意义的标签，该标签从DAG1映射到DAG2。假设您有一组边缘E *，它们与DAG1和DAG2中标记的边缘相交，您将需要执行一系列的行移位(上移或下移)或列移位(左移或右移)，以便所有DAG1和DAG2中E *中的边相互映射。请注意，对于以Matrix表示的DAG，整个行或整个列的移位位置仍使表示等效。
剩下的操作将是根据映射的矩阵重命名顶点，比较这两个矩阵，并标识所需的新边和新顶点(以及可以删除的边和顶点)。