graph - 检查一个图何时是 igraph 中另一个图的子图

Question

我想使用 igraph 检查给定的子图 G 是否是另一个更大的图 G' 的子图。请注意，这不是子图同构问题，因为如果任何顶点或边的标签不同，我希望答案为 False。当且仅当两个图具有相同的边和顶点标签并且 G 是 G' 的子图时，我希望答案为 True。我如何在 igraph 中做到这一点？谢谢。

Answer 1

不确定您所说的顶点/边标签是什么意思，但请注意 igraph 中的 VF2 子同构算法支持顶点/边颜色；如果它们的颜色相同，则允许两个顶点或边匹配。如果您使用 Python 中的 igraph，请检查该类的subisomorphic_vf2方法Graph。如果您使用 R 中的 igraph，请检查该graph.subisomorphic.vf2功能。这两者都由igraph_subisomorphic_vf2C 层中的函数支持。

更新：由于您将字符串作为标签而不是整数（VF2 同构算法所期望的），因此您必须首先将它们转换为整数索引。否则，VF2 应该能够满足您的需求。igraph的Python接口中的一个例子：

>>> g = Graph.Formula("A --> B --> C")
>>> g2 = Graph.Formula("A --> B")
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,1])
[[0, 1]]
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,2])
[]