#NEWLINE# def _break_cycles( self , order , graph ) : #NEWLINE# #INDENT# 'Keep breaking cycles until the graph is a DAG.\n        ' #NEWLINE# broken_edges = [ ] #NEWLINE# strong = [ s for s in nx . strongly_connected_components ( graph ) if ( len ( s ) > 1 ) ] #NEWLINE# if strong : #NEWLINE# #INDENT# graph = graph . subgraph ( graph . nodes_iter ( ) ) #NEWLINE# #UNINDENT# while strong : #NEWLINE# #INDENT# in_edges = [ ] #NEWLINE# start = None #NEWLINE# if ( len ( strong [ 0 ] ) < len ( graph ) ) : #NEWLINE# #INDENT# for s in strong [ 0 ] : #NEWLINE# #INDENT# count = len ( [ u for ( u , v ) in graph . in_edges ( s ) if ( u not in strong [ 0 ] ) ] ) #NEWLINE# in_edges . append ( ( count , s ) ) #NEWLINE# #UNINDENT# in_edges = sorted ( in_edges ) #NEWLINE# if ( in_edges [ ( - 1 ) ] [ 0 ] > 0 ) : #NEWLINE# #INDENT# start = in_edges [ ( - 1 ) ] [ 1 ] #NEWLINE# #UNINDENT# #UNINDENT# if ( start is None ) : #NEWLINE# #INDENT# for node in order : #NEWLINE# #INDENT# if self . pathname : #NEWLINE# #INDENT# node = '.' . join ( ( self . pathname , node ) ) #NEWLINE# #UNINDENT# if ( node in strong [ 0 ] ) : #NEWLINE# #INDENT# start = node #NEWLINE# break #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# for p in graph . predecessors ( start ) : #NEWLINE# #INDENT# if ( p in strong [ 0 ] ) : #NEWLINE# #INDENT# graph . remove_edge ( p , start ) #NEWLINE# broken_edges . append ( ( p , start ) ) #NEWLINE# #UNINDENT# #UNINDENT# strong = [ s for s in nx . strongly_connected_components ( graph ) if ( len ( s ) > 1 ) ] #NEWLINE# #UNINDENT# return ( graph , broken_edges )