python 如何正确使用nx方法check_planarity of networkx?

tmb3ates  于 2023-04-28  发布在  Python
关注(0)|答案(2)|浏览(165)

我想要什么?

我有一个有很多顶点和很多边的图。顶点是协调的。我特灵着检查图形的平面性,我总是得到True作为答案。

示例

下面是一个小例子:

pos = {1: (0, 0), 2: (0, 1), 3: (1, 1), 4: (1, 0)}
    G = nx.Graph().to_undirected()
    G.add_nodes_from(pos)
    G.add_edge(1, 3, weight=1)
    G.add_edge(2, 4, weight=1)
    G.add_edge(2, 3, weight=1)
    print(nx.check_planarity(G, False))
    nx.draw_networkx(G, with_labels=True, pos=pos)
    plt.show()

输出为:

(True, <networkx.algorithms.planarity.PlanarEmbedding object at 0x07CD3E30>)

可以清楚地看到,该图不是平面性的,但是结果仍然是True

我在干什么?

qyswt5oh

qyswt5oh1#

请注意,如果一个图可以在欧氏平面上画出而没有任何边相交,则该图是平面的。
在您的例子中,您的图形是平面的,因为交换节点1和4足以避免边相交。
然而,如果你考虑一个完全图(一个完全图Kn只有n ≤ 4是平面的),你可以看到差异。

>>> K4 = nx.complete_graph(4)
>>> nx.check_planarity(K4)
(True, <networkx.algorithms.planarity.PlanarEmbedding object at 0x1035df1d0>)
>>> K5 = nx.complete_graph(5)
>>> nx.check_planarity(K5)
(False, None)
kupeojn6

kupeojn62#

您可以使用check_planarity的答案来绘制可能的平面布局。

import networkx as nx
import matplotlib.pyplot as plt

pos = {1: (0, 0), 2: (0, 1), 3: (1, 1), 4: (1, 0)}
G = nx.Graph().to_undirected()
G.add_nodes_from(pos)
G.add_edge(1, 3, weight=1)
G.add_edge(2, 4, weight=1)
G.add_edge(2, 3, weight=1)

is_planar, G2 = nx.check_planarity(G, False)
print(is_planar)

# plotting

fig = plt.figure()
ax = fig.add_subplot(121)
ax = plt.gca()
ax.margins(0.20)

# draws the graph as you have drawn it

nx.draw_networkx(G, with_labels=True, pos=pos)

ax = fig.add_subplot(122)
ax = plt.gca()
ax.margins(0.20)

# draws the graph without intersections => graph is planar because 
# it is possible to draw it without edge intersections

nx.draw_networkx(G2, with_labels=True)

plt.show()

相关问题