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.给出 graph
和 subgraph
该算法将从 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子图匹配算法。 |