python - 查找坐标列表是否形成循环

Question

所以我有一个点列表，这些点通常形成一种圆形形状，除了通常很少有来自圆的分支，这些分支基本上只是从圆的边界向某个方向延伸的线。我想创建一个函数，当给定这个坐标/点列表时，它会发现在这组点中是否存在完整路径。

我想过创建一个起点并找出是否存在不重复点的路径(即 (1,1) -> (2, 1) -> (1,1) 不允许)并且可以回到起点；但是，如果起点位于圆的分支中，则此方法无效。

例如，坐标列表

[[0, 0], [0, 1], [1, 2], [2, 3], [3, 3], [3, 4], [4, 4], [3, 2], [3, 1], [3, 0], [2, -1], [1, -1], [0, -1]] 

会形成一个完整的路径，而如果我去掉 [1, -1] 它就不会形成一个完整的路径。

Answer 1

您正在寻找的是 simple cycle .图论包 networkx 提供了一种在 simple_cycles 中查找那些的方法.我们需要做的只是一点点腿部工作来设置图表:

import networkx as nx

def has_simple_cycle(l, start):
    G = nx.DiGraph()
    G.add_edges_from((v1, v2) for v1 in l for v2 in l if v1 != v2 and max(abs(v1[0] - v2[0]), abs(v1[1] - v2[1])) <= 1)
    return any(start in c and len(c) > 2 for c in nx.simple_cycles(G))

在你给出的例子中:

In [26]: has_simple_cycle(l=[(0, 0), (0, 1), (1, 2), (2, 3), (3, 3), (3, 4), (4, 4), (3, 2), (3, 1), (3, 0), (2, -1), (1, -1), (0, -1)], start=(0, 0))
Out[26]: True

In [27]: has_simple_cycle(l=[(0, 0), (0, 1), (1, 2), (2, 3), (3, 3), (3, 4), (4, 4), (3, 2), (3, 1), (3, 0), (2, -1), (0, -1)], start=(0, 0))
Out[27]: False