networkx.algorithms.cycles.simple_cycles

networkx.algorithms.cycles.simple_cycles(G)

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

An simple cycle, or elementary circuit, is a closed path where no node appears twice, except that the first and last node are the same. Two elementary circuits are distinct if they are not cyclic permutations of each other.

Parameters :

G : NetworkX DiGraph

A directed graph

Returns :

A list of circuits, where each circuit is a list of nodes, with the first :

and last node being the same. :

Example: :

>>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]) :

>>> nx.simple_cycles(G) :

[[0, 0], [0, 1, 2, 0], [0, 2, 0], [1, 2, 1], [2, 2]] :

See also

cycle_basis

Notes

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

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

References

[R78]

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