Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Loops by Sim0000
from collections import deque
def find_cycle(network):
all_node = set(sum(network, ()))
max_path = ()
network = [set(relation) for relation in network]
for goal in all_node:
# BFS
q = deque([(goal,)])
while q:
path = q.popleft()
if len(path) > 1 and path[-1] == goal: # found cycle
if len(path) <= 3: continue # bad cycle, for example a-b-a
if len(path) > len(max_path): max_path = path # new record
continue
for next in all_node: # register next path
if (next not in path or next == goal) and {path[-1], next} in network:
q.append(path + (next,))
return max_path
Feb. 4, 2015
Comments:
