Python, networkx

Question

Necesito ayuda ya que no soy experto en programación.

¿Cómo puedo dibujar un gráfico plano? (Se dice que un gráfico es plano si se puede dibujar en el plano de modo que no haya cruces de borde) para un gráfico dado con n nodos y bordes E. y luego voltea los bordes para tener otro gráfico plano (para el ciclo hasta que tengamos todas las posibilidades).

Gracias de antemano, y agradezco su ayuda.

PY

---

>>>#visualize with pygraphviz 
    A=pgv.AGraph() 
    File "<stdin>", line 6 
    A=pgv.AGraph() 
    ^
    SyntaxError: invalid syntax 
>>> A.add_edges_from(G.edges()) 
    Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    NameError: name 'A' is not defined 
>>> A.layout(prog='dot') 
    Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    NameError: name 'A' is not defined 
>>> A.draw('planar.png') 
    Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    NameError: name 'A' is not defined 

Answer 1

Hay varios problemas computacionales difíciles implicados en su pregunta.

Primero, alguna teoría. Si el gráfico G es plano, entonces cada subgráfico de G es plano. Volteando los bordes de G (que tiene bordes e), obtendría 2^e-1 subgrafos planos (si no nos importa la conectividad), que es exponencial (es decir, enorme y "mala"). Probablemente, le gustaría encontrar subgrafos planos "máximos".

Si desea dibujar gráficos planos que también se ven planos es computationally hard, es decir, una cosa es saber que existe una representación gráfica donde los bordes no se cruzan y otra para encontrar dicha representación.

Para la implementación. Parece que networkx no tiene la función que verifica si un gráfico es plano. Algunos otros paquetes que funcionan con gráficos tienen (por ejemplo, sage tiene la función g.is_planar() donde g es un objeto de gráfico). A continuación, escribí una verificación de planaridad "ingenua" (debe haber métodos más eficientes) con networkx, basada en Kuratowski theorem.

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. Si tiene problemas con pygraphviz, intente dibujar con networkx, quizás encuentre los resultados correctos. Así, en lugar de "visualizar con pygraphviz" bloque intente lo siguiente:

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() 

Fin de Edit2.

El resultado es el siguiente.

Ves que hay un cruce en la imagen (pero la gráfica es plana), en realidad es un buen resultado (no se olvide el problema es computacionalmente duro), pygraphviz es un envoltorio de Graphviz que utilizan algoritmos heurísticos. En la línea A.layout(prog='dot'), puede intentar reemplazar 'dot' por 'twopi', 'neato', 'circo', etc., para ver si logra una mejor visualización.

Editar. Consideremos también su pregunta sobre subgrafos planar. Vamos a generar un gráfico no plana:

Creo que la forma más eficiente en la búsqueda de un subgrafo plano es eliminar nodos del "mal menor" (es decir, K (5) o K (3,3))Aquí está mi aplicación:

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) 

Acción:

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

Ahora usted tiene un subgrafo plano L (un objeto gráfico NetworkX) del gráfico no plana G.