networkx.algorithms.isomorphism.ISMAGS#

class ISMAGS(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]#

实现了 ISMAGS 子图匹配算法。[1] ISMAGS 代表“基于索引的具有通用对称性的子图匹配算法”(Index-based Subgraph Matching Algorithm with General Symmetries)。顾名思义，它感知对称性，并且仅生成非对称的同构。

属性:

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 构建。

注意

与 VF2 算法相比，此实现对所提供的图以及比较函数（node_equality 和 edge_equality）施加了额外的条件。

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

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

参考文献

[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

__init__(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]#

参数:

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

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

方法

analyze_symmetry(graph, node_partitions, ...)	给定 node_partitions 和 edge_colors 定义的节点和边相等性，找到描述 graph 对称性的最小排列集和相应的陪集。
find_isomorphisms([symmetry])	查找子图和图之间的所有子图同构
is_isomorphic([symmetry])	如果 graph 与 subgraph 同构则返回 True，否则返回 False。
isomorphisms_iter([symmetry])	如果 graph 和 subgraph 具有相同数量的节点，则与 find_isomorphisms() 函数的作用相同。
largest_common_subgraph([symmetry])	查找 subgraph 和 graph 之间的最大公共导出子图。
subgraph_is_isomorphic([symmetry])	如果 graph 的一个子图与 subgraph 同构则返回 True，否则返回 False。
subgraph_isomorphisms_iter([symmetry])	find_isomorphisms() 的别名。