Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Network Loops by Moff
from collections import defaultdict
class Graph(object):
def __init__(self, edges):
self.adjacent = defaultdict(list)
self.vertices = set()
for a, b in edges:
self.vertices.add(a)
self.vertices.add(b)
self.adjacent[a].append(b)
self.adjacent[b].append(a)
class CyclesFinder(object):
def __init__(self, graph):
self.graph = graph
self.cycles = []
for v in self.graph.vertices:
self.find_path([v])
def check_cycle(self, path):
if len(path) > 2 and path[-1] in self.graph.adjacent[path[0]]:
self.cycles.append(path + [path[0]])
def find_path(self, path):
self.check_cycle(path)
v = path[-1]
for w in self.graph.adjacent[v]:
if w not in path:
self.find_path(path + [w])
def find_cycle(edges):
cf = CyclesFinder(Graph(edges))
if not cf.cycles:
return []
return max(cf.cycles, key=lambda x: len(x))
Aug. 11, 2015
Comments:
