Find simple cycles (elementary circuits) of a directed graph.
simple cycle, or
elementary circuit, is a closed path where no node appears twice. Two elementary circuits are distinct if they are not cyclic permutations of each other.
This version uses a recursive algorithm to build a list of cycles. You should probably use the iterator version called simple_cycles(). Warning: This recursive version uses lots of RAM! It appears in NetworkX for pedagogical value.
- GNetworkX DiGraph
A directed graph
- A list of cycles, where each cycle is represented by a list of nodes
- along the cycle.
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)] ..
>>> G = nx.DiGraph(edges) ..
>>> nx.recursive_simple_cycles(G) ..
- [, , [0, 1, 2], [0, 2], [1, 2]]
The implementation follows pp. 79-80 in .
The time complexity is \(O((n+e)(c+1))\) for \(n\) nodes, \(e\) edges and \(c\) elementary circuits.