algorithm - 是否有任何算法可以计算包含相同节点的两个图之间的编辑距离？

Question

首先，我知道已经有很多工作来计算两个图形之间的编辑距离。但大多数GED算法都适用于一般情况。

现在考虑我的情况，有两个图 G(V1,E1) 和 G(V2,E2)。 Vk是一组包含k个顶点的节点(k为常数)，Vk同时满足Vk⊆V1和Vk ⊆V2。我想在计算它们之间的编辑距离时保持这两个图之间的对应关系。

请问有没有针对这种情况的算法？如果没有，有人对我有什么建议吗？非常感谢

附言

假设vi是Vk中的一个节点。我关心的是当G1转换为G2时vi保持不变，这意味着在操作序列中没有对vi进行操作(例如将G1中的vi替换为G2中的u，删除G1中的vi，插入G2中的vi)将 G1 转换为 G2。

Answer 1

没有算法可以解决你的具体问题，因为没有用例，也没有数学形式。我将如何解决这个问题:

1) 在注释中，您指定 Vk 不变，但指定 Ek(1) Ek(2)，其中 Ek(i) 是 Vk 中 Vi 的节点之间的边。在这种情况下，计算边添加/删除/替换，GED(Vk1, Vk2) 忽略 Vk1/2 之外的边

2) 计算 GED(V1-Vk1, V2-Vk2) 忽略 Vi-Vki 和 Vki 之间的边。其中V1-Vk1是图V1去除Vk中的所有节点和所有与Vk相连的边后

3) 计算 GED(E(V1-Vk1 <-> Vk1), E(V2-Vk2 <-> Vk2))，即计算将“连接 V1-Vk1 和 Vk1 的边”替换为“连接 V2-Vk2 和 Vk2 的边。

4) 将 3 个 GED 加在一起。