Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
recursive solution in Clear category for Network Loops by fleo0917
from collections import defaultdict
def find_cycle(connections):
net = defaultdict(set)
for c in connections:
net[c[0]].add(c[1])
net[c[1]].add(c[0])
def trace(ans, path, depth):
# maximum length of cycle is the number of nodes + 1
# so we can limit recursion depth.
if depth == 0:
return
# found a cycle.
# check its validity and update answer
if path[0] == path[-1] and len(path) > 3:
if len(path) > len(ans):
ans[:] = path
return
# trace next nodes
for nxt in net[path[-1]]:
if nxt in path[1:]:
continue # prevent repeat
if len(path) > 2 and path[-2] == nxt:
continue # prevent going backward
trace(ans, path+[nxt], depth-1)
ans = []
for k in net:
trace(ans, [k], len(net)+1)
return ans
April 28, 2015