networkx.algorithms.isomorphism.ISMAGS

class ISMAGS(graph, subgraph, node_match=None, edge_match=None, cache=None)

实现ISMAGS子图匹配算法。[1] ISMAGS代表“基于索引的具有一般对称性的子图匹配算法”。正如其名所示，该算法具有对称性意识，并且只会生成非对称同构。

Notes

与VF2算法相比，该实现对提供的图和比较函数（node_equality 和:attr:edge_equality ）施加了额外的条件：

• 两个图中的节点键必须是可排序的以及可哈希的。

• 相等性必须是传递的：如果A等于B，且B等于C，那么A必须等于C。

References

[1]

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

Attributes:

graph: networkx.Graph

subgraph: networkx.Graph

node_equality: collections.abc.Callable

用于检查两个节点是否应被视为相等的函数。其签名如下： f(graph1: networkx.Graph, node1, graph2: networkx.Graph, node2) -> bool 。 node1 是 graph1 中的一个节点， node2 是 graph2 中的一个节点。 根据参数 node_match 构造。

edge_equality: collections.abc.Callable

用于检查两个边是否应被视为相等的函数。其签名如下： f(graph1: networkx.Graph, edge1, graph2: networkx.Graph, edge2) -> bool 。 edge1 是 graph1 中的一条边， edge2 是 graph2 中的一条边。 根据参数 edge_match 构造。

__init__(graph, subgraph, node_match=None, edge_match=None, cache=None)

Parameters:

graph: networkx.Graph

图对象。

subgraph: networkx.Graph

子图对象。

node_match: collections.abc.Callable 或 None

用于确定两个节点是否等价的函数。其签名应类似于 f(n1: dict, n2: dict) -> bool ，其中 n1 和 n2 是节点属性字典。参见 categorical_node_match() 及其相关函数。 如果为 None ，则所有节点都被视为相等。

edge_match: collections.abc.Callable 或 None

用于确定两个边是否等价的函数。其签名应类似于 f(e1: dict, e2: dict) -> bool ，其中 e1 和 e2 是边属性字典。参见 categorical_edge_match() 及其相关函数。 如果为 None ，则所有边都被视为相等。

cache: collections.abc.Mapping

用于缓存图对称性的缓存。

Methods

analyze_symmetry(graph, node_partitions, ...)	找到一组最小的置换和相应的陪集，描述给定节点和边等价性的 graph 的对称性，分别由 node_partitions 和 edge_colors 给出。
find_isomorphisms([symmetry])	查找子图与图之间的所有子图同构
is_isomorphic([symmetry])	如果 graph 与 subgraph 同构，则返回 True，否则返回 False。
isomorphisms_iter([symmetry])	与 find_isomorphisms() 功能相同，如果 graph 和 subgraph 的节点数量相同。
largest_common_subgraph([symmetry])	找到 subgraph 和 graph 之间最大的公共诱导子图。
subgraph_is_isomorphic([symmetry])	如果 graph 的子图与 subgraph 同构，则返回 True，否则返回 False。
subgraph_isomorphisms_iter([symmetry])	find_isomorphisms() 的替代名称。