Python, networkx

Ответ 1

В вашем вопросе участвуют несколько сложных вычислительных проблем.

Во-первых, некоторая теория. Если граф G плоский, то каждый подграф G плоский. Отбрасывание ребер из G (с краями e) даст 2^e-1 планарные подграфы (если мы не заботимся о связности), что является экспоненциальным (т.е. Огромным и "плохим" ). Вероятно, вы бы хотели найти "максимальные" планарные подграфы.

Если вы хотите нарисовать плоские графы, которые также выглядят как planar, вычислительно жесткий, то есть одно дело знать, что существует графическое представление, где ребра не пересекаются, а другое - найти такое представление.

К реализации. Кажется, что networkx не имеет функции, которая проверяет, является ли граф плоской. Некоторые другие пакеты, которые работают с графиками (например, sage имеют функцию g.is_planar(), где g - объект графика). Ниже я написал "наивный" (должны быть более эффективные методы) проверку планарности с помощью сетиx, основанную на теореме Куратовского.

import pygraphviz as pgv
import networkx as nx
import itertools as it
from networkx.algorithms import bipartite

def is_planar(G):
    """
    function checks if graph G has K(5) or K(3,3) as minors,
    returns True /False on planarity and nodes of "bad_minor"
    """
    result=True
    bad_minor=[]
    n=len(G.nodes())
    if n>5:
        for subnodes in it.combinations(G.nodes(),6):
            subG=G.subgraph(subnodes)
            if bipartite.is_bipartite(G):# check if the graph G has a subgraph K(3,3)
                X, Y = bipartite.sets(G)
                if len(X)==3:
                    result=False
                    bad_minor=subnodes
    if n>4 and result:
        for subnodes in it.combinations(G.nodes(),5):
            subG=G.subgraph(subnodes)
            if len(subG.edges())==10:# check if the graph G has a subgraph K(5)
                result=False
                bad_minor=subnodes
    return result,bad_minor

#create random planar graph with n nodes and p probability of growing
n=8
p=0.6
while True:
    G=nx.gnp_random_graph(n,p)
    if is_planar(G)[0]:
        break
#visualize with pygraphviz
A=pgv.AGraph()
A.add_edges_from(G.edges())
A.layout(prog='dot')
A.draw('planar.png')

Edit2. Если вы столкнулись с проблемами с pygraphviz, попробуйте сделать с помощью networkx, возможно, вы найдете результаты в порядке. Итак, вместо блока "визуализировать с помощью pygraphviz" попробуйте следующее:

import matplotlib.pyplot as plt
nx.draw(G)
# comment the line above and uncomment one of the 3 lines below (try each of them):
#nx.draw_random(G)
#nx.draw_circular(G)
#nx.draw_spectral(G)
plt.show()

Конец редактирования2.

Результат выглядит следующим образом.

Вы видите там одно пересечение на картинке (но график плоский), это на самом деле хороший результат (не забывайте, что проблема сложна с точки зрения вычислительной мощности), pygraphviz является оберткой для Graphviz, которые используют эвристические алгоритмы. В строке A.layout(prog='dot') вы можете попробовать заменить "dot" на "twopi", "neato", "circo" и т.д., Чтобы увидеть, достигнете ли вы лучшей визуализации.

Edit. Давайте также рассмотрим ваш вопрос о плоских подграфах. Пусть порождает непланарный граф:

while True:
    J=nx.gnp_random_graph(n,p)
    if is_planar(J)[0]==False:
        break

Я думаю, что наиболее эффективным способом поиска планарного подграфа является устранение узлов из "плохого второстепенного" (т.е. K (5) или K (3,3)). Вот моя реализация:

def find_planar_subgraph(G):
    if len(G)<3:
        return G
    else:
        is_planar_boolean,bad_minor=is_planar(G)
        if is_planar_boolean:
            return G
        else:
            G.remove_node(bad_minor[0])
            return find_planar_subgraph(G)

Действие:

L=find_planar_subgraph(J)
is_planar(L)[0]
>> True

Теперь у вас есть планарный подграф L (объект-граф сетки) неплоского графа G.