#NEWLINE# def is_aperiodic( G ) : #NEWLINE# #INDENT# 'Return True if G is aperiodic.\n\n    A directed graph is aperiodic if there is no integer k > 1 that \n    divides the length of every cycle in the graph.\n\n    Parameters\n    ----------\n    G : NetworkX DiGraph\n      Graph\n\n    Returns\n    -------\n    aperiodic : boolean\n      True if the graph is aperiodic False otherwise\n\n    Raises\n    ------\n    NetworkXError\n      If G is not directed\n\n    Notes\n    -----\n    This uses the method outlined in [1]_, which runs in O(m) time\n    given m edges in G. Note that a graph is not aperiodic if it is\n    acyclic as every integer trivial divides length 0 cycles.\n\n    References\n    ----------\n    .. [1] Jarvis, J. P.; Shier, D. R. (1996),\n       Graph-theoretic analysis of finite Markov chains,\n       in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling:\n       A Multidisciplinary Approach, CRC Press.\n    ' #NEWLINE# if ( not G . is_directed ( ) ) : #NEWLINE# #INDENT# raise nx . NetworkXError ( 'is_aperiodic not defined for undirected graphs' ) #NEWLINE# #UNINDENT# s = next ( G . nodes_iter ( ) ) #NEWLINE# levels = { #NEWLINE# #INDENT# s : 0 , #NEWLINE# #UNINDENT# } #NEWLINE# this_level = [ s ] #NEWLINE# g = 0 #NEWLINE# l = 1 #NEWLINE# while this_level : #NEWLINE# #INDENT# next_level = [ ] #NEWLINE# for u in this_level : #NEWLINE# #INDENT# for v in G [ u ] : #NEWLINE# #INDENT# if ( v in levels ) : #NEWLINE# #INDENT# g = gcd ( g , ( ( levels [ G ] - levels [ v ] ) + 1 ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# next_level . append ( v ) #NEWLINE# levels [ v ] = l #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# this_level = next_level #NEWLINE# l += 1 #NEWLINE# #UNINDENT# if ( len ( levels ) == len ( G ) ) : #NEWLINE# #INDENT# return ( g == 1 ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# return ( ( g == 1 ) and nx . is_aperiodic ( G . subgraph ( ( set ( G ) - set ( levels ) ) ) ) )