algorithm - 有向无环图的差异

Question

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

我不是百分百确定，但我认为最长公共(public)子序列可以应用于 DAG。我不太关心生成的编辑序列的长度(只要它足够短)，而更关心算法的运行时间。

一个复杂的问题是除了一个根节点之外，我的所有顶点都没有被标记。根节点也是唯一具有零入边的节点。图的边被标记，图中的“数据”由从根到叶的路径表示。这类似于 trie 但使用有向图而不是树。实际上，我的图与有向无环词图数据结构非常相似。

这是一个例子。

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，移动整行或整列的位置仍然会使表示等价。

剩下的操作就是根据映射后的矩阵重命名顶点，比较两个矩阵，确定需要的新边和新顶点(以及可以移除的边和顶点。