如何验证网络中的图是否有交叉边？

Question

我正在创建一个遗传算法来使用 python 和 networkx 解决旅行商问题。我添加了一个条件来收敛到满意的解决方案：路径不得有交叉边缘。我想知道 networkx 中是否有一个快速函数来验证图形是否具有交叉边，或者至少想知道是否可以创建一个。

该图是使用一系列点 ( path) 创建的，每个点都有一个 x 坐标和 y 坐标。点的序列索引了游览路径。我创建了一个nx.Graph()如下所示的对象：

        G = nx.Graph()
        for i in range(len(path)):
            G.add_node(i, pos=(path[i].x, path[i].y))
            
        for i in range(len(path)-1):
            G.add_edge(i, i+1)
        G.add_edge(len(path)-1, 0)

收敛非最优解的一个例子：

打印出点nx.get_node_attributes(G,'pos')：

{0: (494, 680), 1: (431, 679), 2: (217, 565), 3: (197, 581), 4: (162, 586), 5: (90, 522), 6:(138, 508), 7: (217, 454), 8: (256, 275), 9: (118, 57), 10: (362, 139), 11: (673, 89), 12: (738, 153), 13: (884, 119), 14: (687, 542), 15: (720, 618), 16: (745, 737), 17: (895, 887), 18: (902, 574), 19: (910, 337), 20: (823, 371), 21: (601, 345), 22: (608, 302), 23: (436, 294), 24: (515, 384), 25: (646, 495)}

这是一篇支持收敛条件的文章： http://www.ams.org/publicoutreach/feature-column/fcarc-tsp

Answer 1

我的第一次阅读与@AveragePythonEngineer的相同。通常在旅行商问题和一般图论中，我们不太关心顶点的位置，只关心它们之间的距离。我认为您可能会将图形的绘制与图形混淆（这只是无限可能的绘图的一种实现）。因此，虽然您可以根据需要绘制具有交叉边的平面图（如您的示例），但重点是您可以在平面上绘制它。

\n

在重新阅读您的问题时，我认为您实际上是在引入“禁止交叉路径”作为约束。用行话来说，就是：路径不能自相交。如果这是正确的，那么我认为GIS Stack Exchange 中的这个问题会对您有所帮助。它用shapely，一个非常有用的解决 2D 几何问题的工具。从第一个答案来看：

\n

\n

[查看].is_simple

\n

\n

如果该特征不与自身相交，则返回 True。

\n

\n

\n

from shapely.wkt import loads\nl = loads(\'LINESTRING (9603380.577551289 2719693.31939431, 9602238.01822002 2719133.882441244, 9601011.900844947 2718804.012436028, 9599670.800095448 2718931.680117098, 9599567.204161201 2717889.384686942, 9600852.184025297 2721120.409265322, 9599710.80929024 2720511.270897166, 9602777.832940497 2718125.875545334)\')\nprint(l.is_simple) # False\n

\n

如果您想从头开始解决问题，那么这个类似问题的答案，但在不同的框架中，有一些有趣的线索，特别是Bentley\xe2\x80\x93Ottmann 算法，这可能很有用。

\n

Answer 2

我不确定它是否适合您的问题，但在我看来，它与图的平面性有关。

您可以使用以下方法检查图形是否是平面的：

nx.is_planar(G)

True如果是，则返回。请参阅文档。