spaceghost1337 / python-simple-cycles

algorithm for finding all the simple cycles in a graph

Python Simple Cycles

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

Originally, I implemented this directly from the 1975 Donald B Johnson paper "Finding all the elementary circuits of a directed graph". Later, I found an error in my code, found NetworkX's code, and slightly changed that code so it didn't depend on the NetworkX data structures (so the algorithm could be used in IronPython).

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])