<s> """<STR_LIT>""" <EOL> class Edge : <EOL> def __init__ ( self , source , target ) : <EOL> self . source = source <EOL> self . target = target <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' % ( self . source , self . target ) <EOL> def make_edge_dict ( edge_list ) : <EOL> "<STR_LIT>" <EOL> edges = { } <EOL> for edge in edge_list : <EOL> edges . setdefault ( edge . source , [ ] ) . append ( edge ) <EOL> edges . setdefault ( edge . target , [ ] ) <EOL> return edges <EOL> def depth_first_search ( root , vertices , edges ) : <EOL> seen = { } <EOL> result = [ ] <EOL> def visit ( vertex ) : <EOL> result . append ( ( '<STR_LIT:start>' , vertex ) ) <EOL> seen [ vertex ] = True <EOL> for edge in edges [ vertex ] : <EOL> w = edge . target <EOL> if w in vertices and w not in seen : <EOL> visit ( w ) <EOL> result . append ( ( '<STR_LIT>' , vertex ) ) <EOL> visit ( root ) <EOL> return result <EOL> def vertices_reachable_from ( root , vertices , edges ) : <EOL> for event , v in depth_first_search ( root , vertices , edges ) : <EOL> if event == '<STR_LIT:start>' : <EOL> yield v <EOL> def strong_components ( vertices , edges ) : <EOL> """<STR_LIT>""" <EOL> component_root = { } <EOL> discovery_time = { } <EOL> remaining = vertices . copy ( ) <EOL> stack = [ ] <EOL> for root in vertices : <EOL> if root in remaining : <EOL> for event , v in depth_first_search ( root , remaining , edges ) : <EOL> if event == '<STR_LIT:start>' : <EOL> del remaining [ v ] <EOL> discovery_time [ v ] = len ( discovery_time ) <EOL> component_root [ v ] = v <EOL> stack . append ( v ) <EOL> else : <EOL> vroot = v <EOL> for edge in edges [ v ] : <EOL> w = edge . target <EOL> if w in component_root : <EOL> wroot = component_root [ w ] <EOL> if discovery_time [ wroot ] < discovery_time [ vroot ] : <EOL> vroot = wroot <EOL> if vroot == v : <EOL> component = { } <EOL> while True : <EOL> w = stack . pop ( ) <EOL> del component_root [ w ] <EOL> component [ w ] = True <EOL> if w == v : <EOL> break <EOL> yield component <EOL> else : <EOL> component_root [ v ] = vroot <EOL> def all_cycles ( root , vertices , edges ) : <EOL> """<STR_LIT>""" <EOL> stackpos = { } <EOL> edgestack = [ ] <EOL> result = [ ] <EOL> def visit ( v ) : <EOL> if v not in stackpos : <EOL> stackpos [ v ] = len ( edgestack ) <EOL> for edge in edges [ v ] : <EOL> if edge . target in vertices : <EOL> edgestack . append ( edge ) <EOL> visit ( edge . target ) <EOL> edgestack . pop ( ) <EOL> stackpos [ v ] = None <EOL> else : <EOL> if stackpos [ v ] is not None : <EOL> result . append ( edgestack [ stackpos [ v ] : ] ) <EOL> visit ( root ) <EOL> return result <EOL> def find_roots ( vertices , edges ) : <EOL> """<STR_LIT>""" <EOL> rep = { } <EOL> for component in strong_components ( vertices , edges ) : <EOL> random_vertex , _ = component . popitem ( ) <EOL> rep [ random_vertex ] = random_vertex <EOL> for v in component : <EOL> rep [ v ] = random_vertex <EOL> roots = set ( rep . values ( ) ) <EOL> for v in vertices : <EOL> v1 = rep [ v ] <EOL> for edge in edges [ v ] : <EOL> try : <EOL> v2 = rep [ edge . target ] <EOL> if v1 is not v2 : <EOL> roots . remove ( v2 ) <EOL> except KeyError : <EOL> pass <EOL> return roots <EOL> def compute_depths ( roots , vertices , edges ) : <EOL> """<STR_LIT>""" <EOL> depths = { } <EOL> curdepth = <NUM_LIT:0> <EOL> for v in roots : <EOL> depths [ v ] = <NUM_LIT:0> <EOL> pending = list ( roots ) <EOL> while pending : <EOL> curdepth += <NUM_LIT:1> <EOL> prev_generation = pending <EOL> pending = [ ] <EOL> for v in prev_generation : <EOL> for edge in edges [ v ] : <EOL> v2 = edge . target <EOL> if v2 in vertices and v2 not in depths : <EOL> depths [ v2 ] = curdepth <EOL> pending . append ( v2 ) <EOL> return depths <EOL> def is_acyclic ( vertices , edges ) : <EOL> class CycleFound ( Exception ) : <EOL> pass <EOL> def visit ( vertex ) : <EOL> visiting [ vertex ] = True <EOL> for edge in edges [ vertex ] : <EOL> w = edge . target <EOL> if w in visiting : <EOL> raise CycleFound <EOL> if w in unvisited : <EOL> del unvisited [ w ] <EOL> visit ( w ) <EOL> del visiting [ vertex ] <EOL> try : <EOL> unvisited = vertices . copy ( ) <EOL> while unvisited : <EOL> visiting = { } <EOL> root = unvisited . popitem ( ) [ <NUM_LIT:0> ] <EOL> visit ( root ) <EOL> except CycleFound : <EOL> return False <EOL> else : <EOL> return True <EOL> def break_cycles ( vertices , edges ) : <EOL> """<STR_LIT>""" <EOL> remaining_edges = edges . copy ( ) <EOL> progress = True <EOL> roots_finished = set ( ) <EOL> while progress : <EOL> roots = list ( find_roots ( vertices , remaining_edges ) ) <EOL> progress = False <EOL> for root in roots : <EOL> if root in roots_finished : <EOL> continue <EOL> cycles = all_cycles ( root , vertices , remaining_edges ) <EOL> if not cycles : <EOL> roots_finished . add ( root ) <EOL> continue <EOL> allcycles = { } <EOL> edge2cycles = { } <EOL> for cycle in cycles : <EOL> allcycles [ id ( cycle ) ] = cycle <EOL> for edge in cycle : <EOL> edge2cycles . setdefault ( edge , [ ] ) . append ( id ( cycle ) ) <EOL> edge_weights = { } <EOL> for edge , cycle in edge2cycles . iteritems ( ) : <EOL> edge_weights [ edge ] = len ( cycle ) <EOL> while allcycles : <EOL> max_weight = <NUM_LIT:0> <EOL> max_edge = None <EOL> for edge , weight in edge_weights . iteritems ( ) : <EOL> if weight > max_weight : <EOL> max_edge = edge <EOL> max_weight = weight <EOL> if max_edge is None : <EOL> break <EOL> yield max_edge <EOL> progress = True <EOL> for broken_cycle_id in edge2cycles [ max_edge ] : <EOL> broken_cycle = allcycles . pop ( broken_cycle_id , ( ) ) <EOL> for edge in broken_cycle : <EOL> edge_weights [ edge ] -= <NUM_LIT:1> <EOL> lst = remaining_edges [ max_edge . source ] [ : ] <EOL> lst . remove ( max_edge ) <EOL> remaining_edges [ max_edge . source ] = lst <EOL> assert is_acyclic ( vertices , remaining_edges ) <EOL> def break_cycles_v ( vertices , edges ) : <EOL> """<STR_LIT>""" <EOL> v_depths = vertices <EOL> progress = True <EOL> roots_finished = set ( ) <EOL> while progress : <EOL> roots = list ( find_roots ( v_depths , edges ) ) <EOL> if v_depths is vertices : <EOL> v_depths = compute_depths ( roots , vertices , edges ) <EOL> assert len ( v_depths ) == len ( vertices ) <EOL> progress = False <EOL> for root in roots : <EOL> if root in roots_finished : <EOL> continue <EOL> cycles = all_cycles ( root , v_depths , edges ) <EOL> if not cycles : <EOL> roots_finished . add ( root ) <EOL> continue <EOL> allcycles = [ ] <EOL> for cycle in cycles : <EOL> cycledepth = max ( [ v_depths [ edge . source ] for edge in cycle ] ) <EOL> allcycles . append ( ( cycledepth , cycle ) ) <EOL> allcycles . sort ( ) <EOL> for _ , cycle in allcycles : <EOL> try : <EOL> choices = [ ( v_depths [ edge . source ] , edge . source ) <EOL> for edge in cycle ] <EOL> except KeyError : <EOL> pass <EOL> else : <EOL> max_depth , max_vertex = max ( choices ) <EOL> del v_depths [ max_vertex ] <EOL> yield max_vertex <EOL> progress = True <EOL> assert is_acyclic ( v_depths , edges ) <EOL> def show_graph ( vertices , edges ) : <EOL> from pypy . translator . tool . graphpage import GraphPage , DotGen <EOL> class MathGraphPage ( GraphPage ) : <EOL> def compute ( self ) : <EOL> dotgen = DotGen ( '<STR_LIT>' ) <EOL> names = { } <EOL> for i , v in enumerate ( vertices ) : <EOL> names [ v ] = '<STR_LIT>' % i <EOL> for i , v in enumerate ( vertices ) : <EOL> dotgen . emit_node ( names [ v ] , label = str ( v ) ) <EOL> for edge in edges [ v ] : <EOL> dotgen . emit_edge ( names [ edge . source ] , names [ edge . target ] ) <EOL> self . source = dotgen . generate ( target = None ) <EOL> MathGraphPage ( ) . display ( ) </s>
