检查一个networkx图是否是另一个图的子图

Question

我有一个networkx图G，我想检查另一个networkx图 ，H是否可以嵌入其中。简单的例子包括：

• 检查是否G包含三角形（这可以通过 完成networkx.triangles）
• 检查是否G包含长度的路径/循环k
• 检查是否G包含带有叶子的星星k（这可以通过度数序列来完成）

ETC。

我知道问题一般是NP-complete，但我想看看是否存在比 naive 更好的东西，或者您是否对如何编写这样的方法有建议。

Answer 1

我一直在用 python 做一些广泛的图表工作，我建议不要使用它networkx来解决更大的问题。由于该库是纯 python 的，因此它非常适合较小的图和可移植性，但对于较大的子图同构，我发现它graph-tool效果很好。

您在图形工具中查找的函数调用位于拓扑部分下：

graph_tool.topology.subgraph_isomorphism