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

Question

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

我想过创建一个起点并寻找是否存在不重复点的路径（即 (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. The graph theory package networkx provides a method for finding those in 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

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

Find if list of coordinates form a loop

python

list

graph-theory

path-finding