Skip to main content
`Ctrl`+`K`

# is_aperiodic

is_aperiodic(G)

  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:
    bool

      True if the graph is aperiodic False otherwise

  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.

  Examples

  A graph consisting of one cycle, the length of which is 2. Therefore `k = 2` divides the length of every cycle in the graph and thus the graph is not aperiodic:

      >>> DG = nx.DiGraph([(1, 2), (2, 1)])
      >>> nx.is_aperiodic(DG)
      False

  A graph consisting of two cycles: one of length 2 and the other of length 3. The cycle lengths are coprime, so there is no single value of k where `k > 1` that divides each cycle length and therefore the graph is aperiodic:

      >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (1, 4), (4, 1)])
      >>> nx.is_aperiodic(DG)
      True

  A graph consisting of two cycles: one of length 2 and the other of length 4. The lengths of the cycles share a common factor `k = 2`, and therefore the graph is not aperiodic:

      >>> DG = nx.DiGraph([(1, 2), (2, 1), (3, 4), (4, 5), (5, 6), (6, 3)])
      >>> nx.is_aperiodic(DG)
      False

  An acyclic graph, therefore the graph is not aperiodic:

      >>> DG = nx.DiGraph([(1, 2), (2, 3)])
      >>> nx.is_aperiodic(DG)
      False