Function to find all the cycles in a networkx graph. Health warning: this thing is an NP-complete depth-first search, work hard to make the graphs you put into it small.

cycles.py

def find_all_cycles(G, source=None, cycle_length_limit=None):
    """forked from networkx dfs_edges function. Assumes nodes are integers, or at least
    types which work with min() and > ."""
    if source is None:
        # produce edges for all components
        nodes=[i[0] for i in nx.connected_components(G)]
    else:
        # produce edges for components with source
        nodes=[source]
    # extra variables for cycle detection:
    cycle_stack = []
    output_cycles = set()
    
    def get_hashable_cycle(cycle):
        """cycle as a tuple in a deterministic order."""
        m = min(cycle)
        mi = cycle.index(m)
        mi_plus_1 = mi + 1 if mi < len(cycle) - 1 else 0
        if cycle[mi-1] > cycle[mi_plus_1]:
            result = cycle[mi:] + cycle[:mi]
        else:
            result = list(reversed(cycle[:mi_plus_1])) + list(reversed(cycle[mi_plus_1:]))
        return tuple(result)
    
    for start in nodes:
        if start in cycle_stack:
            continue
        cycle_stack.append(start)
        
        stack = [(start,iter(G[start]))]
        while stack:
            parent,children = stack[-1]
            try:
                child = next(children)
                
                if child not in cycle_stack:
                    cycle_stack.append(child)
                    stack.append((child,iter(G[child])))
                else:
                    i = cycle_stack.index(child)
                    if i < len(cycle_stack) - 2: 
                      output_cycles.add(get_hashable_cycle(cycle_stack[i:]))
                
            except StopIteration:
                stack.pop()
                cycle_stack.pop()
    
    return [list(i) for i in output_cycles]

Hey Joe,

How is this code licensed?

Thanks!
Mike

Thank you very much, this helped a lot, as networkx find_cycle did not find all cycles in some cases.

In line 6 "i[0]" must be changed to "list(i)[0]", otherwise you get "TypeError: 'set' object is not subscriptable"

Really helpful. Thank you very much for your share!

Hey @joe-jordan ,
this function is very helpful and I would like to use it in some code. How is it licensed?
Best,
Hannah

Hey @joe-jordan ,
Really cool solution. How is it licensed?

Thanks for your share!
Victoria

Hello all.

I don't maintain this code, and it was written for python 2. It also sounds like the networkx interface has changed (see pali08's comment above).

The licensing here is BSD, specifically:

Copyright (c) 2013 Joe F Jordan. All rights reserved.

Redistribution and use in source and binary forms are permitted provided that the above copyright notice and this paragraph are duplicated in all such forms and that any documentation, advertising materials, and other materials related to such distribution and use acknowledge that the software was developed by Joe F Jordan. The name of Joe F Jordan may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED `'AS IS″ AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.