Python Boyer-Myrvold 平面性检验或 Kuratowski 子图识别库
Python Library for Boyer-Myrvold planarity test or Kuratowski subgraph identification
我正在 Python 中使用 NetworkX 图，我想找到我拥有的任何给定图的 Kuratowski 子图。
Boyer-Myrvold 平面图测试算法可以 return 现有的 Kuratowski 子图，如果该图不是平面的（顶点数 n 中的 O(n)），所以我希望可能已经存在是该算法或 Python 中类似算法的实现。到目前为止，我一直找不到一个，而且我有点不愿意从原始研究论文中重新实现它。
如果它可以轻松地与用于图形的 NetworkX 库接口，那就更好了。
John Boyer 的平面性代码 (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
我正在 Python 中使用 NetworkX 图，我想找到我拥有的任何给定图的 Kuratowski 子图。
Boyer-Myrvold 平面图测试算法可以 return 现有的 Kuratowski 子图，如果该图不是平面的（顶点数 n 中的 O(n)），所以我希望可能已经存在是该算法或 Python 中类似算法的实现。到目前为止，我一直找不到一个，而且我有点不愿意从原始研究论文中重新实现它。
如果它可以轻松地与用于图形的 NetworkX 库接口，那就更好了。
John Boyer 的平面性代码 (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