graph.py 文件源码

def find_4_cycles(edges):
    """return all unique four-cycles in graph"""
    # for each node, add a list of reachable nodes
    # for all pairs of reachable node test if they share a reachable node -> cycle
    reachables = defaultdict(set)
    for edge in edges:
        reachables[edge[0]].add(edge[1])
        reachables[edge[1]].add(edge[0])

    loops = {}
    for a, reachable in reachables.iteritems():
        for b, c in itertools.combinations(reachable, 2):
            for d in reachables[b].intersection(reachables[c]).difference(set([a])):
                loops[tuple(sorted([a, b, d, c]))] = [a, b, d, c]

    return loops.values()