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, a chord is an additional edge between two nodes in the cycle. A chordless 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 of C.

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.

  1. 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.

  2. We interpret directed two-cycles to be chordless cycles, except in multi-digraphs when any edge in a two-cycle has a parallel copy.

  3. We interpret parallel pairs of undirected edges as two-cycles, except when a third (or more) parallel edge exists between the two nodes.

  4. 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:

  1. Recursion is avoided, per Python’s limitations

  2. 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

  3. The search is optionally bounded at a specified length

  4. Support for directed graphs is provided by extending cycles along

    forward edges, and blocking nodes along forward and reverse edges

  5. 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

simple_cycles

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]]
On this page