<s> from collections import OrderedDict <EOL> class TopologicalSortError ( Exception ) : <EOL> def __init__ ( self , message ) : <EOL> self . message = message <EOL> def __str__ ( self ) : <EOL> return "<STR_LIT>" . format ( self . __class__ . __name__ , self . message ) <EOL> def topological_sort ( graph ) : <EOL> """<STR_LIT>""" <EOL> incomming = OrderedDict ( <EOL> [ <EOL> ( node , list ( edges ) ) for node , edges in graph . iteritems ( ) <EOL> ] <EOL> ) <EOL> nodes = [ node for node in incomming . iterkeys ( ) ] <EOL> stack = [ ] <EOL> while nodes : <EOL> n = nodes [ <NUM_LIT:0> ] <EOL> remaining = [ node for node in reversed ( incomming [ n ] ) if node in nodes ] <EOL> if remaining : <EOL> if n not in stack : <EOL> stack . append ( n ) <EOL> else : <EOL> raise TopologicalSortError ( <EOL> "<STR_LIT>" <EOL> "<STR_LIT>" . format ( <EOL> '<STR_LIT>' . join ( <EOL> [ <EOL> str ( x ) for x in ( <EOL> stack + [ n ] <EOL> ) <EOL> ] <EOL> ) <EOL> ) <EOL> ) <EOL> for m in remaining : <EOL> nodes . remove ( m ) <EOL> nodes . insert ( <NUM_LIT:0> , m ) <EOL> else : <EOL> yield nodes . pop ( <NUM_LIT:0> ) </s>
