Python, networkx

Question

Ho bisogno di aiuto poiché non sono esperto di programmazione.

Come posso disegnare un grafico planare (Un grafico è detto planare se può essere disegnato nel piano in modo tale che non vi siano attraversamenti di bordi) per un dato grafico con n nodi e bordi E. e quindi capovolgere i bordi per avere un altro grafico planare (per il ciclo fino a quando non si ottengono tutte le possibilità).

Grazie in anticipo, e apprezzo il vostro aiuto.

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

Ci sono diversi hard problemi computazionali coinvolti nella sua interrogazione.

In primo luogo, un po 'di teoria. Se il grafico G è planare, allora ogni sottografo di G è planare. bordi Flipping da G (che ha e bordi), darebbe 2^e-1 sottografi planari (se non ci preoccupiamo per la connettività), che è esponenziale (cioè enorme e "cattivo"). Probabilmente, ti piacerebbe trovare sottografi planari "massimali".

Se desideri disegnare grafici planari che sembrano anch'essi planari è computationally hard, vale a dire una cosa è sapere che esiste una rappresentazione grafica in cui i bordi non si incrociano e un altro per trovare tale rappresentazione.

Per implementazione. Sembra che networkx non abbia la funzione che controlla se un grafico è planare. Alcuni altri pacchetti che funzionano con i grafici hanno (ad esempio, sage ha la funzione g.is_planar() dove g è un oggetto grafico). Di seguito, ho scritto un "ingenuo" (ci devono essere metodi più efficienti) controllo di planarità con networkx, basato su 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. Se hai problemi con pygraphviz, prova a disegnare con networkx, forse trovi i risultati ok. Così, invece di "visualizzare con pygraphviz" blocco provare quanto segue:

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

Fine EDIT2.

Il risultato assomiglia a questo.

Vedete c'è un passaggio sopra l'immagine (ma il grafico è planare), in realtà è un buon risultato (non dimenticate il problema è computazionalmente difficile), pygraphviz è un wrapper per Graphviz che utilizzano algoritmi euristici. Nella riga A.layout(prog='dot') puoi provare a sostituire "punto" con "twopi", "neato", "circo" ecc. Per vedere se ottieni una visualizzazione migliore.

Modifica. Prendiamo anche in considerazione la tua domanda sui sottografi planari. Facciamo generare un grafico non planare:

Credo che il modo più efficace nella ricerca di un sottografo planare è quello di eliminare i nodi del "cattivo minore" (cioè K (5) o K (3,3)).Qui è la mia realizzazione:

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) 

Azione:

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

Ora avete un planare sottografo L (un oggetto grafico NetworkX) del grafo non planare G.