<s> """<STR_LIT>""" <EOL> from . . exc import CircularDependencyError <EOL> from . . import util <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> def sort_as_subsets ( tuples , allitems ) : <EOL> edges = util . defaultdict ( set ) <EOL> for parent , child in tuples : <EOL> edges [ child ] . add ( parent ) <EOL> todo = set ( allitems ) <EOL> while todo : <EOL> output = set ( ) <EOL> for node in list ( todo ) : <EOL> if not todo . intersection ( edges [ node ] ) : <EOL> output . add ( node ) <EOL> if not output : <EOL> raise CircularDependencyError ( <EOL> "<STR_LIT>" , <EOL> find_cycles ( tuples , allitems ) , <EOL> _gen_edges ( edges ) <EOL> ) <EOL> todo . difference_update ( output ) <EOL> yield output <EOL> def sort ( tuples , allitems ) : <EOL> """<STR_LIT>""" <EOL> for set_ in sort_as_subsets ( tuples , allitems ) : <EOL> for s in set_ : <EOL> yield s <EOL> def find_cycles ( tuples , allitems ) : <EOL> edges = util . defaultdict ( set ) <EOL> for parent , child in tuples : <EOL> edges [ parent ] . add ( child ) <EOL> nodes_to_test = set ( edges ) <EOL> output = set ( ) <EOL> for node in nodes_to_test : <EOL> stack = [ node ] <EOL> todo = nodes_to_test . difference ( stack ) <EOL> while stack : <EOL> top = stack [ - <NUM_LIT:1> ] <EOL> for node in edges [ top ] : <EOL> if node in stack : <EOL> cyc = stack [ stack . index ( node ) : ] <EOL> todo . difference_update ( cyc ) <EOL> output . update ( cyc ) <EOL> if node in todo : <EOL> stack . append ( node ) <EOL> todo . remove ( node ) <EOL> break <EOL> else : <EOL> node = stack . pop ( ) <EOL> return output <EOL> def _gen_edges ( edges ) : <EOL> return set ( [ <EOL> ( right , left ) <EOL> for left in edges <EOL> for right in edges [ left ] <EOL> ] ) </s>
