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
- Returns
True if the graph is aperiodic False otherwise
- Return type
- Raises
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.