<s> """<STR_LIT>""" <EOL> from pygraph . algorithms . utils import heappush , heappop <EOL> from pygraph . classes . exceptions import NodeUnreachable <EOL> from pygraph . classes . exceptions import NegativeWeightCycleError <EOL> from pygraph . classes . digraph import digraph <EOL> import bisect <EOL> def minimal_spanning_tree ( graph , root = None ) : <EOL> """<STR_LIT>""" <EOL> visited = [ ] <EOL> spanning_tree = { } <EOL> if ( root is not None ) : <EOL> visited . append ( root ) <EOL> nroot = root <EOL> spanning_tree [ root ] = None <EOL> else : <EOL> nroot = <NUM_LIT:1> <EOL> while ( nroot is not None ) : <EOL> ledge = _lightest_edge ( graph , visited ) <EOL> if ( ledge == None ) : <EOL> if ( root is not None ) : <EOL> break <EOL> nroot = _first_unvisited ( graph , visited ) <EOL> if ( nroot is not None ) : <EOL> spanning_tree [ nroot ] = None <EOL> visited . append ( nroot ) <EOL> else : <EOL> spanning_tree [ ledge [ <NUM_LIT:1> ] ] = ledge [ <NUM_LIT:0> ] <EOL> visited . append ( ledge [ <NUM_LIT:1> ] ) <EOL> return spanning_tree <EOL> def _first_unvisited ( graph , visited ) : <EOL> """<STR_LIT>""" <EOL> for each in graph : <EOL> if ( each not in visited ) : <EOL> return each <EOL> return None <EOL> def _lightest_edge ( graph , visited ) : <EOL> """<STR_LIT>""" <EOL> lightest_edge = None <EOL> weight = None <EOL> for each in visited : <EOL> for other in graph [ each ] : <EOL> if ( other not in visited ) : <EOL> w = graph . edge_weight ( ( each , other ) ) <EOL> if ( weight is None or w < weight or weight < <NUM_LIT:0> ) : <EOL> lightest_edge = ( each , other ) <EOL> weight = w <EOL> return lightest_edge <EOL> def shortest_path ( graph , source ) : <EOL> """<STR_LIT>""" <EOL> dist = { source : <NUM_LIT:0> } <EOL> previous = { source : None } <EOL> q = [ ( <NUM_LIT:0> , source ) ] <EOL> finished = set ( ) <EOL> while len ( q ) > <NUM_LIT:0> : <EOL> du , u = q . pop ( <NUM_LIT:0> ) <EOL> if u not in finished : <EOL> finished . add ( u ) <EOL> for v in graph [ u ] : <EOL> if v not in finished : <EOL> alt = du + graph . edge_weight ( ( u , v ) ) <EOL> if ( v not in dist ) or ( alt < dist [ v ] ) : <EOL> dist [ v ] = alt <EOL> previous [ v ] = u <EOL> bisect . insort ( q , ( alt , v ) ) <EOL> return previous , dist <EOL> def shortest_path_bellman_ford ( graph , source ) : <EOL> """<STR_LIT>""" <EOL> distance = { source : <NUM_LIT:0> } <EOL> predecessor = { source : None } <EOL> for i in range ( <NUM_LIT:1> , graph . order ( ) - <NUM_LIT:1> ) : <EOL> for src , dst in graph . edges ( ) : <EOL> if ( src in distance ) and ( dst not in distance ) : <EOL> distance [ dst ] = distance [ src ] + graph . edge_weight ( ( src , dst ) ) <EOL> predecessor [ dst ] = src <EOL> elif ( src in distance ) and ( dst in distance ) and distance [ src ] + graph . edge_weight ( ( src , dst ) ) < distance [ dst ] : <EOL> distance [ dst ] = distance [ src ] + graph . edge_weight ( ( src , dst ) ) <EOL> predecessor [ dst ] = src <EOL> for src , dst in graph . edges ( ) : <EOL> if src in distance and dst in distance and distance [ src ] + graph . edge_weight ( ( src , dst ) ) < distance [ dst ] : <EOL> raise NegativeWeightCycleError ( "<STR_LIT>" % ( src , dst ) ) <EOL> return predecessor , distance <EOL> def heuristic_search ( graph , start , goal , heuristic ) : <EOL> """<STR_LIT>""" <EOL> queue = [ ( <NUM_LIT:0> , start , <NUM_LIT:0> , None ) ] <EOL> g = { } <EOL> explored = { } <EOL> while queue : <EOL> _ , current , dist , parent = heappop ( queue ) <EOL> if current == goal : <EOL> path = [ current ] + [ n for n in _reconstruct_path ( parent , explored ) ] <EOL> path . reverse ( ) <EOL> return path <EOL> if current in explored : <EOL> continue <EOL> explored [ current ] = parent <EOL> for neighbor in graph [ current ] : <EOL> if neighbor in explored : <EOL> continue <EOL> ncost = dist + graph . edge_weight ( ( current , neighbor ) ) <EOL> if neighbor in g : <EOL> qcost , h = g [ neighbor ] <EOL> if qcost <= ncost : <EOL> continue <EOL> else : <EOL> h = heuristic ( neighbor , goal ) <EOL> g [ neighbor ] = ncost , h <EOL> heappush ( queue , ( ncost + h , neighbor , ncost , current ) ) <EOL> raise NodeUnreachable ( start , goal ) <EOL> def _reconstruct_path ( node , parents ) : <EOL> while node is not None : <EOL> yield node <EOL> node = parents [ node ] <EOL> def maximum_flow ( graph , source , sink , caps = None ) : <EOL> """<STR_LIT>""" <EOL> if caps == None : <EOL> caps = { } <EOL> for edge in graph . edges ( ) : <EOL> caps [ edge ] = graph . edge_weight ( ( edge [ <NUM_LIT:0> ] , edge [ <NUM_LIT:1> ] ) ) <EOL> f = { } . fromkeys ( graph . edges ( ) , <NUM_LIT:0> ) <EOL> label = { } . fromkeys ( graph . nodes ( ) , [ ] ) <EOL> label [ source ] = [ '<STR_LIT:->' , float ( '<STR_LIT>' ) ] <EOL> u = { } . fromkeys ( graph . nodes ( ) , False ) <EOL> d = { } . fromkeys ( graph . nodes ( ) , float ( '<STR_LIT>' ) ) <EOL> q = [ source ] <EOL> finished = False <EOL> while not finished : <EOL> for i in range ( len ( q ) ) : <EOL> if not u [ q [ i ] ] : <EOL> v = q . pop ( i ) <EOL> break <EOL> for w in graph . neighbors ( v ) : <EOL> if label [ w ] == [ ] and f [ ( v , w ) ] < caps [ ( v , w ) ] : <EOL> d [ w ] = min ( caps [ ( v , w ) ] - f [ ( v , w ) ] , d [ v ] ) <EOL> label [ w ] = [ v , '<STR_LIT:+>' , d [ w ] ] <EOL> q . append ( w ) <EOL> for w in graph . incidents ( v ) : <EOL> if label [ w ] == [ ] and f [ ( w , v ) ] > <NUM_LIT:0> : <EOL> d [ w ] = min ( f [ ( w , v ) ] , d [ v ] ) <EOL> label [ w ] = [ v , '<STR_LIT:->' , d [ w ] ] <EOL> q . append ( w ) <EOL> u [ v ] = True <EOL> if label [ sink ] != [ ] : <EOL> delta = label [ sink ] [ - <NUM_LIT:1> ] <EOL> w = sink <EOL> while w != source : <EOL> v = label [ w ] [ <NUM_LIT:0> ] <EOL> if label [ w ] [ <NUM_LIT:1> ] == '<STR_LIT:->' : <EOL> f [ ( w , v ) ] = f [ ( w , v ) ] - delta <EOL> else : <EOL> f [ ( v , w ) ] = f [ ( v , w ) ] + delta <EOL> w = v <EOL> label = { } . fromkeys ( graph . nodes ( ) , [ ] ) <EOL> label [ source ] = [ '<STR_LIT:->' , float ( '<STR_LIT>' ) ] <EOL> q = [ source ] <EOL> u = { } . fromkeys ( graph . nodes ( ) , False ) <EOL> d = { } . fromkeys ( graph . nodes ( ) , float ( '<STR_LIT>' ) ) <EOL> finished = True <EOL> for node in graph . nodes ( ) : <EOL> if label [ node ] != [ ] and u [ node ] == False : <EOL> finished = False <EOL> cut = { } <EOL> for node in graph . nodes ( ) : <EOL> if label [ node ] == [ ] : <EOL> cut [ node ] = <NUM_LIT:1> <EOL> else : <EOL> cut [ node ] = <NUM_LIT:0> <EOL> return ( f , cut ) <EOL> def cut_value ( graph , flow , cut ) : <EOL> """<STR_LIT>""" <EOL> S = [ ] <EOL> T = [ ] <EOL> for node in cut . keys ( ) : <EOL> if cut [ node ] == <NUM_LIT:0> : <EOL> S . append ( node ) <EOL> elif cut [ node ] == <NUM_LIT:1> : <EOL> T . append ( node ) <EOL> value = <NUM_LIT:0> <EOL> for node in S : <EOL> for neigh in graph . neighbors ( node ) : <EOL> if neigh in T : <EOL> value = value + flow [ ( node , neigh ) ] <EOL> for inc in graph . incidents ( node ) : <EOL> if inc in T : <EOL> value = value - flow [ ( inc , node ) ] <EOL> return value <EOL> def cut_tree ( igraph , caps = None ) : <EOL> """<STR_LIT>""" <EOL> graph = digraph ( ) <EOL> graph . add_graph ( igraph ) <EOL> if not caps : <EOL> caps = { } <EOL> for edge in graph . edges ( ) : <EOL> caps [ edge ] = igraph . edge_weight ( edge ) <EOL> f = { } <EOL> n = { } <EOL> N = <NUM_LIT:0> <EOL> for node in graph . nodes ( ) : <EOL> n [ N ] = node <EOL> N = N + <NUM_LIT:1> <EOL> p = { } . fromkeys ( range ( N ) , <NUM_LIT:0> ) <EOL> p [ <NUM_LIT:0> ] = None <EOL> for s in range ( <NUM_LIT:1> , N ) : <EOL> t = p [ s ] <EOL> S = [ ] <EOL> ( flow , cut ) = maximum_flow ( graph , n [ s ] , n [ t ] , caps ) <EOL> for i in range ( N ) : <EOL> if cut [ n [ i ] ] == <NUM_LIT:0> : <EOL> S . append ( i ) <EOL> value = cut_value ( graph , flow , cut ) <EOL> f [ s ] = value <EOL> for i in range ( N ) : <EOL> if i == s : <EOL> continue <EOL> if i in S and p [ i ] == t : <EOL> p [ i ] = s <EOL> if p [ t ] in S : <EOL> p [ s ] = p [ t ] <EOL> p [ t ] = s <EOL> f [ s ] = f [ t ] <EOL> f [ t ] = value <EOL> b = { } <EOL> for i in range ( <NUM_LIT:1> , N ) : <EOL> b [ ( n [ i ] , n [ p [ i ] ] ) ] = f [ i ] <EOL> return b </s>
