ISMAGS算法#
提供了一个ISMAGS算法的Python实现。[1]
它能够找到两个图之间的（子图）同构，考虑到子图的对称性。在大多数情况下，VF2算法比这个实现更快（至少在小图上），但在某些情况下，存在指数数量的同构是关于对称性等价的。在这种情况下，ISMAGS算法将为每个对称组提供一个解决方案。
`python
>>> 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
`
此外，这个实现还提供了一个接口，用于在考虑对称性的情况下找到任意两个图之间的最大公共诱导子图[Re111c1f21506-2]_。给定 graph 和 subgraph ，算法将移除 subgraph 中的节点，直到 subgraph 同构于 graph 的一个子图。由于只考虑 subgraph 的对称性，值得思考如何提供你的图：
`python
>>> 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
`
然而，当不考虑对称性时，这并不重要：
`python
>>> 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
`
Notes#
当前实现仅适用于无向图。尽管如此，该算法在一般情况下也适用于有向图。
两个图的节点键需要是完全可排序且可哈希的。
假设节点和边的相等性是传递的：如果A等于B，且B等于C，则A等于C。
References#
M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle, M. Pickavet, “基于索引的具有一般对称性的子图匹配算法（ISMAGS）：利用对称性实现更快的子图枚举”, PLoS One 9(5): e97896, 2014. https://doi.org/10.1371/journal.pone.0097896
ISMAGS object#
|
实现ISMAGS子图匹配算法。[Rcc65a4edf17b-1] ISMAGS代表“基于索引的具有一般对称性的子图匹配算法”。正如其名所示，该算法具有对称性意识，并且只会生成非对称同构。 |