我不是编程专家,因此需要帮助。
对于给定的具有 n 个节点和 E 条边的图,我如何绘制一个平面图(如果可以在平面上绘制而没有边交叉,则称该图是平面图)。然后翻转边缘以获得另一个平面图。(循环直到我们获得所有可能性)。
在此先致谢,感谢您的帮助。
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
您的问题中涉及到几个困难的计算问题。
首先,一些理论。如果图 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')
编辑2。 如果您在使用 pygraphviz 时遇到问题,请尝试使用 networkx 进行绘制,也许您会发现结果不错。因此,不要使用“使用 pygraphviz 可视化” block ,而是尝试以下操作:
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')
行中,您可以尝试将 'dot' 替换为 'twopi'、'neato'、'circo' 等,看看是否能实现更好的可视化效果。
编辑。让我们也考虑一下关于平面子图的问题。
让我们生成一个非平面图:
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
现在你有一个非平面图 G 的平面子图 L(一个 networkx 图对象)。