ismags算法#

提供ISMAGS算法的Python实现。 [1]

它能够发现两个图之间的(子图)同构,同时考虑子图的对称性。在大多数情况下,vf2算法比这个实现更快(至少在小图上),但在某些情况下,同构的指数数量是对称等价的。在这种情况下,ismags算法只能为每个对称群提供一个解。

>>> petersen = nx.petersen_graph()
>>> ismags = nx.isomorphism.ISMAGS(petersen, petersen)
>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=False))
>>> len(isomorphisms)
120
>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=True))
>>> answer = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}]
>>> answer == isomorphisms
True

此外,该实现还提供了寻找最大公共导出子图的接口 [2] 在任意两个图之间,同样考虑到对称性。vt.给出 graphsubgraph 该算法将从 subgraph 直到 subgraph 同构于的子图 graph 。因为只有对称性 subgraph 考虑到这一点,值得考虑的是如何提供图表:

>>> graph1 = nx.path_graph(4)
>>> graph2 = nx.star_graph(3)
>>> ismags = nx.isomorphism.ISMAGS(graph1, graph2)
>>> ismags.is_isomorphic()
False
>>> largest_common_subgraph = list(ismags.largest_common_subgraph())
>>> answer = [{1: 0, 0: 1, 2: 2}, {2: 0, 1: 1, 3: 2}]
>>> answer == largest_common_subgraph
True
>>> ismags2 = nx.isomorphism.ISMAGS(graph2, graph1)
>>> largest_common_subgraph = list(ismags2.largest_common_subgraph())
>>> answer = [
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 0: 1, 3: 2},
...     {2: 0, 0: 1, 1: 2},
...     {2: 0, 0: 1, 3: 2},
...     {3: 0, 0: 1, 1: 2},
...     {3: 0, 0: 1, 2: 2},
... ]
>>> answer == largest_common_subgraph
True

然而,当不考虑对称性时,这并不重要:

>>> largest_common_subgraph = list(ismags.largest_common_subgraph(symmetry=False))
>>> answer = [
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 2: 1, 0: 2},
...     {2: 0, 1: 1, 3: 2},
...     {2: 0, 3: 1, 1: 2},
...     {1: 0, 0: 1, 2: 3},
...     {1: 0, 2: 1, 0: 3},
...     {2: 0, 1: 1, 3: 3},
...     {2: 0, 3: 1, 1: 3},
...     {1: 0, 0: 2, 2: 3},
...     {1: 0, 2: 2, 0: 3},
...     {2: 0, 1: 2, 3: 3},
...     {2: 0, 3: 2, 1: 3},
... ]
>>> answer == largest_common_subgraph
True
>>> largest_common_subgraph = list(ismags2.largest_common_subgraph(symmetry=False))
>>> answer = [
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 0: 1, 3: 2},
...     {2: 0, 0: 1, 1: 2},
...     {2: 0, 0: 1, 3: 2},
...     {3: 0, 0: 1, 1: 2},
...     {3: 0, 0: 1, 2: 2},
...     {1: 1, 0: 2, 2: 3},
...     {1: 1, 0: 2, 3: 3},
...     {2: 1, 0: 2, 1: 3},
...     {2: 1, 0: 2, 3: 3},
...     {3: 1, 0: 2, 1: 3},
...     {3: 1, 0: 2, 2: 3},
... ]
>>> answer == largest_common_subgraph
True

笔记#

  • 当前的实现只适用于无向图。一般来说,该算法也适用于有向图。

  • 两个提供的图的节点键都需要是完全可排序的和散列的。

  • 假设节点和边相等是可传递的:如果a等于b,b等于c,则a等于c。

工具书类#

1

M.Houbraken,S.Demeyer,T.Michoel,P.Audenaert,D.Colle,M.Pickavet,“具有一般对称性的基于索引的子图匹配算法(ISMAGS):利用对称性加快子图计数”,《公共科学类库》第9期(5):E978962014。https://doi.org/10.1371/journal.pone.0097896

2

https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph

ismags对象#

ISMAGS(graph, subgraph[, node_match, ...])

实现了ismags子图匹配算法。