Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.dag.is_aperiodic¶

is_aperiodic(G)[source]

Returns True if G is aperiodic.

A directed graph is aperiodic if there is no integer k > 1 that divides the length of every cycle in the graph.

Parameters: G (NetworkX DiGraph) – A directed graph True if the graph is aperiodic False otherwise bool NetworkXError – If G is not directed

Notes

This uses the method outlined in [1], which runs in $$O(m)$$ time given $$m$$ edges in G. Note that a graph is not aperiodic if it is acyclic as every integer trivial divides length 0 cycles.

References

 [1] Jarvis, J. P.; Shier, D. R. (1996), “Graph-theoretic analysis of finite Markov chains,” in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling: A Multidisciplinary Approach, CRC Press.