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

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