Python，networkx

Question

我需要幫助，因爲我不擅長編程。

如何繪製具有n個節點和E邊的給定圖的平面圖（如果可以在平面中繪製圖，那麼不存在邊交叉）。然後翻轉邊緣以得到另一個平面圖形（for循環，直到我們獲得所有可能性）。

在此先感謝，我感謝您的幫助。

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

有涉及您的問題多顆計算問題。

首先，一些理論。如果圖G是平面的，那麼G的每個子圖都是平面的。從G（具有e邊緣）的邊緣翻轉，將給出2^e-1平面子圖（如果我們不關心連通性），這是指數（即巨大和「壞」）。可能，你想找到「最大」的平面子圖。

如果您想繪製平面圖也看起來像平面是computationally hard，即知道存在一個圖形表示，其中邊緣不交叉而另一個圖形表示找到這樣的表示。

執行。看起來像networkx沒有檢查圖形是否平面的功能。其他一些使用圖形的軟件包（例如，sage具有g.is_planar()函數，其中g是圖形對象）。下面，我寫了一個基於Kuratowski theorem的「天真」（必須有更高效的方法）與networkx平面性檢查。

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可視化」 塊嘗試以下：中EDIT2

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

結束。

結果看起來像這樣。

你看到有一個過路的圖片（但圖是平面），它實際上是一個很好的結果（不要忘了問題是計算硬），pygraphviz是一個包裝Graphviz它們使用的啓發式算法。在A.layout(prog='dot')行中，您可以嘗試用'twopi'，'neato'，'circo'等替換'dot'，以查看您是否實現了更好的可視化。

編輯。我們也考慮一下關於平面子圖的問題。 讓我們產生非平面圖形：

我想找到一個平面子圖最有效的方法是消除「壞的微小的」節點（即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 

現在你有非平面圖形G.