用於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庫

回答

相關問題