Python Simple Cycles

This is an algorithm for finding all the simple cycles in a directed graph.

This was implemented directly from the 1975 Donald B Johnson paper "Finding all the elementary circuits of a directed graph" with modificatios so that it didn't depend on the NetworkX data structures (so the algorithm could be used in IronPython). Tarjan's algorithm was modified to a non-recursive implementation.

NetworkX's original implementation

The original paper which described the algorithm:
Donald B Johnson. "Finding all the elementary circuits of a directed graph." SIAM Journal on Computing. 1975.

Example

>>> from johnson import simple_cycles
>>> graph = {0: [7, 3, 5], 1: [2], 2: [7, 1], 3: [0, 5], 4: [6, 8], 5: [0, 3, 7], 6: [4, 8], 7: [0, 2, 5, 8], 8: [4, 6, 7]}
>>> print(tuple(simple_cycles(graph)))
([0, 7, 5, 3], [0, 7, 5], [0, 7], [0, 5, 7], [0, 5, 3], [0, 5], [0, 3, 5, 7], [0, 3, 5], [0, 3], [1, 2], [2, 7], [3, 5], [8, 7], [8, 6, 4], [8, 6], [8, 4, 6], [8, 4], [5, 7], [4, 6])