Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Network Loops by bukebuer
# migrated from python 2.7
from collections import deque, defaultdict
from functools import reduce
def find_cycle(connections):
connections = list(map(set, connections))
all_nodes = reduce(lambda x,y: x|y, connections)
cdict = defaultdict(set)
for a,b in connections:
cdict[a].add(b)
cdict[b].add(a)
best_trace = []
while all_nodes:
a = all_nodes.pop()
to_search = deque([a, p] for p in cdict[a])
while to_search:
trace = to_search.popleft()
cur_p = trace[-1]
for p in cdict[cur_p]:
if p == a and len(trace) > 2 and len(trace) + 1 > len(best_trace):
best_trace = trace + [p]
elif p not in trace:
to_search.appendleft(trace + [p])
all_nodes = all_nodes - set(best_trace)
return best_trace
Feb. 6, 2015
Comments: