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.