#NEWLINE# @ classmethod #NEWLINE# def sort_based_on_dependency( self , classes ) : #NEWLINE# #INDENT# "sorts the given Migration classes based on their dependencies\n            to other Models.\n\n        returns a list of MigrationClasses in the order they can be migrated\n        or raises suitable exceptions if this couldn't be completed\n        " #NEWLINE# def topological_sort( edges ) : #NEWLINE# #INDENT# '\n            does a topological sort on the supplied edges http://goo.gl/lkOt1\n            ' #NEWLINE# G = nx . DiGraph ( ) #NEWLINE# for path in edges : #NEWLINE# #INDENT# G . add_nodes_from ( path ) #NEWLINE# G . add_path ( path ) #NEWLINE# #UNINDENT# return nx . topological_sort ( G ) #NEWLINE# #UNINDENT# dependency_graphs = [ ( mig . depends_on + [ mig . model ] ) for mig in classes ] #NEWLINE# ordered_models = topological_sort ( dependency_graphs ) #NEWLINE# ordered_migrations = [ ] #NEWLINE# for model in ordered_models : #NEWLINE# #INDENT# matching_mig = [ cla for cla in classes if ( cla . model == ordered_migrations ) ] #NEWLINE# if ( len ( matching_mig ) == 1 ) : #NEWLINE# #INDENT# ordered_migrations . append ( matching_mig [ 0 ] ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( len ( matching_mig ) == 0 ) : #NEWLINE# #INDENT# raise AttributeError ( ( "There is no migration available for '%s'" % model ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# raise AttributeError ( ( "InvalidState: '%s' has more than one migration" % model ) ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# return ordered_migrations