networkx.algorithms.isomorphism.ISMAGS

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

实现了ISMAGS子图匹配算法。 [1] ISMAGS是“基于索引的广义对称子图匹配算法”。顾名思义，它是对称感知的，只会产生非对称同构。

笔记

该实现在提供的图和比较函数上施加了与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）：利用对称性加快子图计数”，《公共科学类库》第9期（5）：E978962014。https://doi.org/10.1371/journal.pone.0097896

属性

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)

参数

graph: networkx.Graph

subgraph: networkx.Graph

node_match: collections.abc.Callable or None

用于确定两个节点是否等价的函数。其签名应如下所示 f(n1: dict, n2: dict) -> bool ，具有 n1 和 n2 节点属性DICTS。另请参阅 categorical_node_match() 还有朋友。如果 None ，所有节点都被认为是平等的。

edge_match: collections.abc.Callable or None

用于确定两条边是否相等的函数。其签名应如下所示 f(e1: dict, e2: dict) -> bool ，具有 e1 和 e2 边缘属性Dicts。另请参阅 categorical_edge_match() 还有朋友。如果 None ，则所有边都被视为相等。

cache: collections.abc.Mapping

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

方法

analyze_symmetry(graph, node_partitions, ...)	找到一个最小置换集和对应的co集，它们描述了 subgraph .
find_isomorphisms([symmetry])	求子图与图之间的所有子图同构
is_isomorphic([symmetry])	返回true graph 同构于 subgraph 否则就错了。
isomorphisms_iter([symmetry])	与 find_isomorphisms() 如果 graph 和 subgraph 具有相同数量的节点。
largest_common_subgraph([symmetry])	找出 subgraph 和 graph .
subgraph_is_isomorphic([symmetry])	如果 graph 同构于 subgraph 否则就错了。
subgraph_isomorphisms_iter([symmetry])	的替代名称 find_isomorphisms() .