Skip to main content
`Ctrl`+`K`

# recursive_simple_cycles

recursive_simple_cycles(G)

  Find simple cycles (elementary circuits) of a directed graph.

  A `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.

  Parameters:
    G NetworkX DiGraph

      A directed graph

  Returns:
    A list of cycles, where each cycle is represented by a list of nodes
    along the cycle.
    Example:

        >>> 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], [2], [0, 1, 2], [0, 2], [1, 2]]

  See also

  `simple_cycles`, `cycle_basis`

  Notes

  The implementation follows pp. 79-80 in [1].

  The time complexity is \(O((n+e)(c+1))\) for \(n\) nodes, \(e\) edges and \(c\) elementary circuits.

  References

  [1]

  Finding all the elementary circuits of a directed graph. D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. https://doi.org/10.1137/0204007