simple_cycles#
- simple_cycles(G)[source]#
Find simple cycles (elementary circuits) of a directed graph.
A
simple cycle
, orelementary 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 is a nonrecursive, iterator/generator version of Johnson’s algorithm [1]. There may be better algorithms for some cases [2] [3].
- Parameters:
- GNetworkX DiGraph
A directed graph
- Yields:
- list of nodes
Each cycle is represented by a list of nodes along the cycle.
See also
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] (1,2)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
[2]Enumerating the cycles of a digraph: a new preprocessing strategy. G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.
[3]A search strategy for the elementary cycles of a directed graph. J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS, v. 16, no. 2, 192-204, 1976.
Examples
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)] >>> G = nx.DiGraph(edges) >>> sorted(nx.simple_cycles(G)) [[0], [0, 1, 2], [0, 2], [1, 2], [2]]
To filter the cycles so that they don’t include certain nodes or edges, copy your graph and eliminate those nodes or edges before calling. For example, to exclude self-loops from the above example:
>>> H = G.copy() >>> H.remove_edges_from(nx.selfloop_edges(G)) >>> sorted(nx.simple_cycles(H)) [[0, 1, 2], [0, 2], [1, 2]]