So I have a list of points that generally form a sort of circular shape except there are often little offshoots from the circle that are essentially just lines from say the border of the circle going in a certain direction. I want to create a function that when given this list of coordinates/points finds whether there exists a complete path in this set of points.
I've thought about creating a start point and finding whether there exists a path that doesn't repeat points (ie (1,1) -> (2, 1) -> (1,1) disallowed) and could get back to the start point; however, if the start point is in an offshoot of the circle, this wouldn't work.
For instance, a list of coordinates
[[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]]
would form a complete path while if I take out [1, -1] it would not form a complete path.
What you're looking for is a simple cycle. The graph theory package networkx provides a method for finding those in simple_cycles. All we need to do is a tiny bit of leg work to set up the graph:
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))
On your given examples:
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