用于Boyer-Myrvold平面度测试或Kuratowski子图识别的Python库

我正在使用Python中的NetworkX图形，我想找到任何给定图形的Kuratowski子图。用于Boyer-Myrvold平面度测试或Kuratowski子图识别的Python库

Boyer-Myrvold平面图测试算法可以返回现有的Kuratowski子图，如果图不是平面的（顶点数n中的O（n）），所以我希望可能已经有一个实现算法或Python中的类似算法。我一直无法找到一个，而我稍微不愿意从原始研究报告中重新实施它。

如果它可以轻松地与NetworkX库进行图形接口，那更好。

来源

2015-06-05 patapouf_ai

约翰博伊尔的平面代码（https://code.google.com/p/planarity/）的一部分有一个Python包装器，可能是你正在寻找的东西。它在https://github.com/hagberg/planarity。

它有一个NetworkX接口，允许您测试平面性，如果不是，则可以找到Kurotowski子图。例如

https://github.com/hagberg/planarity/blob/master/examples/networkx_interface.py

import planarity 
import networkx as nx 
# Example of the complete graph of 5 nodes, K5 
G=nx.complete_graph(5) 
# K5 is not planar 
print(planarity.is_planar(G)) # False 
# find forbidden Kuratowski subgraph 
K=planarity.kuratowski_subgraph(G) 
print(K.edges()) # K5 edges

来源

2015-06-06 03:28:37 Aric

谢谢！它看起来真的很有希望，但我似乎无法完成它的工作。我碰到下面的错误，而试图将其导入：进口平面回溯（最近通话最后一个）：文件“”，1号线，在文件“./planarity/planarity/__init__.py”第2行，在 from .planarity import PGraph ImportError：没有名为planarity的模块 –

我猜这个问题可能源于平面性是.pyx文件而不是.py文件这一事实？ –

好的。我通过以下步骤解决了问题： –

用于Boyer-Myrvold平面度测试或Kuratowski子图识别的Python库

回答

相关问题