python - 如何验证一个图在 networkx 中是否有交叉边？

Question

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

图形是用点列表(路径)创建的，每个点都有一个 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's 相同.通常在旅行商问题和一般的图论中，我们不太关心顶点的位置，只关心它们之间的距离。而且我认为您可能会将图形的绘图与图形混淆(它只是无限可能绘图的一种实现)。因此，虽然您可以根据需要绘制具有交叉边的平面图(如您的示例)，但关键是您可以在平面上绘制它。

在重新阅读您的问题时，我认为您实际上是在引入“无交叉路径”作为约束条件。用行话换句话说:路径不能自相交。如果那是对的，那么我认为 this question in GIS Stack Exchange会帮助你。它使用 shapely ，一个非常有用的二维几何问题工具。来自第一个答案:

[Check out] .is_simple

Returns True if the feature does not cross itself.

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

如果您想从头开始解决问题，那么 this answer对于类似的问题，但在不同的框架中，有一些有趣的线索，尤其是 Bentley–Ottmann algorithm ，这可能会有用。