Python iGraph中多图同构的检验

Question

我正在python上运行igraph，并且我注意到iGraph并没有为多个图正确地实现图同构检查。例如：

$ python

Python 2.7.6 (default, Jun 22 2015, 17:58:13) [GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.

>>> import igraph

>>> g = igraph.Graph(3)
>>> g.add_edges([(0, 0), (0, 0), (0, 1), (0, 2), (1, 2), (1, 2), (1, 2)])

>>> h = igraph.Graph(3)
>>> h.add_edges([(0, 1), (0, 2), (0, 2), (0, 2), (1, 2), (1, 2), (1, 2)])

很明显，图g和图h不是同构的(g包含循环，h不同构)。然而igraph将它们识别为同构的。

>>> g.isomorphic(h)
True

同样的情况发生在isomorphic_vf2上：

>>> g.isomorphic_vf2(h)
True

我需要一个函数，multigraph_Isomorphic(g，h)，它将返回真当且仅当多个图g和h是同构的。

我非常感谢任何帮助。谢谢!

Answer 1

构建在图像中的同构算法只支持简单的图(即没有循环或多条边)。您可以通过在isomorphic_vf2中使用顶点和边缘颜色来克服这一限制。其想法如下：

1. 首先，将颜色k分配给具有k个环边的顶点。
2. 然后，如果有多个边，则创建一个名为weight的边界属性，其值为每个边等于1，然后调用g.simplify(loops=False, weight="sum")将多个边折叠为简单的边，并将它们的原始多重性分配给名为weight的边缘属性。
3. 然后为h做同样的事情。
4. 最后，您调用g.isomorphic(h, color1=g.vs["color"], color2=h.vs["color"], edge_color1=g.es["weight"], edge_color2=h.es["weight"])。这将要求VF2算法不仅根据顶点和边缘的连接，而且根据它们的颜色来匹配顶点和边缘。