chordless_cycles#
- chordless_cycles(G, length_bound=None)[source]#
Find simple chordless cycles of a graph.
A
simple cycle
is a closed path where no node appears twice. In a simple cycle, achord
is an additional edge between two nodes in the cycle. Achordless cycle
is a simple cycle without chords. Said differently, a chordless cycle is a cycle C in a graph G where the number of edges in the induced graph G[C] is equal to the length ofC
.Note that some care must be taken in the case that G is not a simple graph nor a simple digraph. Some authors limit the definition of chordless cycles to have a prescribed minimum length; we do not.
We interpret self-loops to be chordless cycles, except in multigraphs with multiple loops in parallel. Likewise, in a chordless cycle of length greater than 1, there can be no nodes with self-loops.
We interpret directed two-cycles to be chordless cycles, except in multi-digraphs when any edge in a two-cycle has a parallel copy.
We interpret parallel pairs of undirected edges as two-cycles, except when a third (or more) parallel edge exists between the two nodes.
Generalizing the above, edges with parallel clones may not occur in chordless cycles.
In a directed graph, two chordless cycles are distinct if they are not cyclic permutations of each other. In an undirected graph, two chordless cycles are distinct if they are not cyclic permutations of each other nor of the other’s reversal.
Optionally, the cycles are bounded in length.
We use an algorithm strongly inspired by that of Dias et al [1]. It has been modified in the following ways:
Recursion is avoided, per Python’s limitations
- The labeling function is not necessary, because the starting paths
are chosen (and deleted from the host graph) to prevent multiple occurrences of the same path
The search is optionally bounded at a specified length
- Support for directed graphs is provided by extending cycles along
forward edges, and blocking nodes along forward and reverse edges
- Support for multigraphs is provided by omitting digons from the set
of forward edges
- Parameters:
- GNetworkX DiGraph
A directed graph
- length_boundint or None, optional (default=None)
If length_bound is an int, generate all simple cycles of G with length at most length_bound. Otherwise, generate all simple cycles of G.
- Yields:
- list of nodes
Each cycle is represented by a list of nodes along the cycle.
- Raises:
- ValueError
when length_bound < 0.
See also
Notes
When length_bound is None, and the graph is simple, the time complexity is \(O((n+e)(c+1))\) for \(n\) nodes, \(e\) edges and \(c\) chordless cycles.
References
[1]Efficient enumeration of chordless cycles E. Dias and D. Castonguay and H. Longo and W.A.R. Jradi https://arxiv.org/abs/1309.1051
Examples
>>> sorted(list(nx.chordless_cycles(nx.complete_graph(4)))) [[1, 0, 2], [1, 0, 3], [2, 0, 3], [2, 1, 3]]