Python Library для теста на плоскость Boyer-Myrvold или идентификация подграфа Kuratowski

Question

Я работаю с графиками NetworkX в Python, и мне хотелось бы найти подграфы Kuratowski любого заданного графика, который у меня есть.

Алгоритм тестирования планарного графа Boyer-Myrvold может возвращать существующий подграф Kuratowski, если граф не является плоским (O (n) в числе вершин n), поэтому я надеялся, что уже может быть реализация этого алгоритм или аналогичный алгоритм в Python. Я до сих пор не смог его найти, и я немного неохотно реорганизую его из оригинальной исследовательской работы.

Это даже лучше, если он может легко взаимодействовать с библиотекой NetworkX для графиков.

Answer 1

Существует обертка Python для частичного плана Джоан Бойера (https://code.google.com/p/planarity/), который может быть тем, что вы ищете. Это на 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