如何在networkx中验证图形是否具有交叉边？

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

- Fabricio Brum

---

这看起来像一个不错的起点：https://en.wikipedia.org/wiki/Multiple_line_segment_intersection - 0x5453

我会使用Shapely来查找相交的线。 - Tom McLean

相关问题：如何检查在给定固定节点位置的情况下，假设边缘是直线并使用networkx绘制，是否存在任何两个边缘的交点？ - kirogasa

@fabricio Brum，如果你还在，请你修复/重新上传你在stackoverflow上的图片（T2XJc）。 - undefined

Answer 1

我的第一读法和@AveragePythonEngineer的一样。通常在旅行商问题和图论中，我们不太关心顶点的位置，只关心它们之间的距离。我认为你可能会把图的绘制与图本身混淆（它只是无限可能的绘制之一）。因此，尽管你可以画一个有交叉边的平面图（就像你的示例一样），但重点是你可以在平面上画出它。

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

[查阅] .is_simple

如果要素不交叉，则返回True。

from shapely.wkt import loads
l = 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)')
print(l.is_simple) # False

如果您想从零开始解决问题，那么这个答案对于一个类似的问题，在不同框架下提供了一些有趣的线索，特别是Bentley-Ottmann算法可能会有用。

- Matt Hall

---

感谢您的回答，我同意您的评估。 - AveragePythonEnjoyer

通过 Bentley-Ottmann 算法解决它似乎是最理想的方式。我将把图形适应到 shapely 中并进行比较。非常感谢！出于好奇，我的算法在 https://github.com/onofabricio/caixeiroViajante 中。(它是用葡萄牙语编写的) 只需运行 main.py 脚本并为随机点解决问题。 - Fabricio Brum

Answer 2

我不确定这是否适用于您的问题，但在我看来，它似乎与平面图有关。

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

nx.is_planar(G)

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

- AveragePythonEnjoyer

---

我之前尝试过这个，它总是返回True，我不知道为什么。 - Fabricio Brum