如何在Networkx中测试一个图是否是另一个图的子图？

Question

我刚开始用networkx构建有向图，我正在尝试如何比较两个图。更具体地说，如何判断小图是否是大图的子图(不确定确切的术语)。

例如，假设我有以下有向图：

​

我希望能够检查一系列较小的图是否是这个初始图的子图。如果它们是(图B)，返回一个真值(图B)，如果它们不是，返回一个False值(图C)：

​

图B=图A的子图

​

图C !=图A的子图

示例代码

import networkx

A = nx.DiGraph()
A.add_edges_from([('A','B'),('B','C'),('C','A')])
nx.draw_networkx(A)


B = nx.DiGraph()
B.add_edges_from([('A','B')])
nx.draw_networkx(B)

C = nx.DiGraph()
C.add_edges_from([('A','B'),('A','C')])
nx.draw_networkx(C)

我看了一下文档，似乎找不到我需要的东西。我一直在考虑的另一种方法是将节点表示为字符串序列，然后搜索主图字符串序列中的每个子字符串--然而，我无法想象这是解决这个问题最有效、最有效/最稳定的方法。

Answer 1

你在找一个子图同构。

nx.isomorphism.DiGraphMatcher(A, B).subgraph_is_isomorphic()
# True

nx.isomorphism.DiGraphMatcher(A, C).subgraph_is_isomorphic()
# False

请注意，对于大型图，操作可能比较慢，因为问题是NP-完全的。