logo标签列表

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

pythongraph-theorynetworkx
5
我有一个名为networkx的图形G，我希望检查另一个名为networkx的图形H是否可以被嵌入其中。简单的例子包括：
- 检查G是否包含一个三角形（可以通过networkx.triangles完成） - 检查G是否包含长度为k的路径/循环 - 检查G是否包含有k个叶子的星形图（可以通过度序列完成）
等等。
我知道这个问题通常是NP-complete的，但我想知道是否存在比朴素算法更好的方法，或者您对如何编写这样的方法有什么建议。
为什么您认为它是NP完全问题？据我所知，天真的方法 is_subraph = lambda G, H: all(h_edge in G.edges() for h_edge in H.edges) 是O(m,n)的，这显然是多项式时间。 - Marat
那不会寻找同构。例如，您将如何使用该方法检查图中（任何）三角形的存在？ - Bach
你的意思是图表没有标签吗？（不确定是否可以使用networkx处理它们） - Marat
我并没有说它们是未标记的。我只是问是否可以将 H 嵌入到 G 中，并且嵌入忽略标签。这是可以做到的 - 只是很难（NP完全）。 - Bach
抱歉，我被标记子图的问题困住了。由于它是一个NP完全问题，在G和H上是否有任何假设或特殊属性？检测率的放宽是否可接受？ - Marat
1
一个可能的假设是 G 很大（我相信在这种情况下它不是 NP-complete）。另一个可能的假设是 H 属于某个特定类别，比如树、环等。然而，这个问题是关于 networkx 的，而不是嵌入算法 ;) 我正在寻找 networkx 提供的工具，即使它们很简单。 - Bach
1个回答
5
我一直在使用Python处理图表，并建议在处理大型问题时不要使用networkx库。由于该库是纯Python编写的，因此非常适合小型图表和可移植性，但对于大型子图同构问题，我发现graph-tool效果很好。

在graph-tool中，您需要查找的函数调用位于拓扑部分：

graph_tool.topology.subgraph_isomorphism

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接