<s> """<STR_LIT>""" <EOL> __author__ = """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' ] <EOL> from itertools import chain <EOL> from math import log <EOL> import networkx as nx <EOL> from ... utils import BinaryHeap <EOL> from ... utils import generate_unique_node <EOL> from ... utils import not_implemented_for <EOL> from ... utils import arbitrary_element <EOL> def _detect_unboundedness ( R ) : <EOL> """<STR_LIT>""" <EOL> s = generate_unique_node ( ) <EOL> G = nx . DiGraph ( ) <EOL> G . add_nodes_from ( R ) <EOL> inf = R . graph [ '<STR_LIT>' ] <EOL> f_inf = float ( '<STR_LIT>' ) <EOL> for u in R : <EOL> for v , e in R [ u ] . items ( ) : <EOL> w = f_inf <EOL> for k , e in e . items ( ) : <EOL> if e [ '<STR_LIT>' ] == inf : <EOL> w = min ( w , e [ '<STR_LIT>' ] ) <EOL> if w != f_inf : <EOL> G . add_edge ( u , v , weight = w ) <EOL> if nx . negative_edge_cycle ( G ) : <EOL> raise nx . NetworkXUnbounded ( <EOL> '<STR_LIT>' <EOL> '<STR_LIT>' ) <EOL> @ not_implemented_for ( '<STR_LIT>' ) <EOL> def _build_residual_network ( G , demand , capacity , weight ) : <EOL> """<STR_LIT>""" <EOL> if sum ( G . node [ u ] . get ( demand , <NUM_LIT:0> ) for u in G ) != <NUM_LIT:0> : <EOL> raise nx . NetworkXUnfeasible ( "<STR_LIT>" ) <EOL> R = nx . MultiDiGraph ( ) <EOL> R . add_nodes_from ( ( u , { '<STR_LIT>' : - G . node [ u ] . get ( demand , <NUM_LIT:0> ) , <EOL> '<STR_LIT>' : <NUM_LIT:0> } ) for u in G ) <EOL> inf = float ( '<STR_LIT>' ) <EOL> for u , v , e in G . selfloop_edges ( data = True ) : <EOL> if e . get ( weight , <NUM_LIT:0> ) < <NUM_LIT:0> and e . get ( capacity , inf ) == inf : <EOL> raise nx . NetworkXUnbounded ( <EOL> '<STR_LIT>' <EOL> '<STR_LIT>' ) <EOL> if G . is_multigraph ( ) : <EOL> edge_list = [ ( u , v , k , e ) <EOL> for u , v , k , e in G . edges ( data = True , keys = True ) <EOL> if u != v and e . get ( capacity , inf ) > <NUM_LIT:0> ] <EOL> else : <EOL> edge_list = [ ( u , v , <NUM_LIT:0> , e ) for u , v , e in G . edges ( data = True ) <EOL> if u != v and e . get ( capacity , inf ) > <NUM_LIT:0> ] <EOL> inf = max ( sum ( abs ( R . node [ u ] [ '<STR_LIT>' ] ) for u in R ) , <EOL> <NUM_LIT:2> * sum ( e [ capacity ] for u , v , k , e in edge_list <EOL> if capacity in e and e [ capacity ] != inf ) ) or <NUM_LIT:1> <EOL> for u , v , k , e in edge_list : <EOL> r = min ( e . get ( capacity , inf ) , inf ) <EOL> w = e . get ( weight , <NUM_LIT:0> ) <EOL> R . add_edge ( u , v , key = ( k , True ) , capacity = r , weight = w , flow = <NUM_LIT:0> ) <EOL> R . add_edge ( v , u , key = ( k , False ) , capacity = <NUM_LIT:0> , weight = - w , flow = <NUM_LIT:0> ) <EOL> R . graph [ '<STR_LIT>' ] = inf <EOL> _detect_unboundedness ( R ) <EOL> return R <EOL> def _build_flow_dict ( G , R , capacity , weight ) : <EOL> """<STR_LIT>""" <EOL> inf = float ( '<STR_LIT>' ) <EOL> flow_dict = { } <EOL> if G . is_multigraph ( ) : <EOL> for u in G : <EOL> flow_dict [ u ] = { } <EOL> for v , es in G [ u ] . items ( ) : <EOL> flow_dict [ u ] [ v ] = dict ( <EOL> ( k , ( <NUM_LIT:0> if ( u != v or e . get ( capacity , inf ) <= <NUM_LIT:0> or <EOL> e . get ( weight , <NUM_LIT:0> ) >= <NUM_LIT:0> ) else e [ capacity ] ) ) <EOL> for k , e in es . items ( ) ) <EOL> for v , es in R [ u ] . items ( ) : <EOL> if v in flow_dict [ u ] : <EOL> flow_dict [ u ] [ v ] . update ( ( k [ <NUM_LIT:0> ] , e [ '<STR_LIT>' ] ) <EOL> for k , e in es . items ( ) <EOL> if e [ '<STR_LIT>' ] > <NUM_LIT:0> ) <EOL> else : <EOL> for u in G : <EOL> flow_dict [ u ] = dict ( <EOL> ( v , ( <NUM_LIT:0> if ( u != v or e . get ( capacity , inf ) <= <NUM_LIT:0> or <EOL> e . get ( weight , <NUM_LIT:0> ) >= <NUM_LIT:0> ) else e [ capacity ] ) ) <EOL> for v , e in G [ u ] . items ( ) ) <EOL> flow_dict [ u ] . update ( ( v , e [ '<STR_LIT>' ] ) for v , es in R [ u ] . items ( ) <EOL> for e in es . values ( ) if e [ '<STR_LIT>' ] > <NUM_LIT:0> ) <EOL> return flow_dict <EOL> def capacity_scaling ( G , demand = '<STR_LIT>' , capacity = '<STR_LIT>' , weight = '<STR_LIT>' , <EOL> heap = BinaryHeap ) : <EOL> r"""<STR_LIT>""" <EOL> R = _build_residual_network ( G , demand , capacity , weight ) <EOL> inf = float ( '<STR_LIT>' ) <EOL> flow_cost = sum ( <EOL> <NUM_LIT:0> if e . get ( capacity , inf ) <= <NUM_LIT:0> or e . get ( weight , <NUM_LIT:0> ) >= <NUM_LIT:0> <EOL> else e [ capacity ] * e [ weight ] <EOL> for u , v , e in G . selfloop_edges ( data = True ) ) <EOL> wmax = max ( chain ( [ - inf ] , <EOL> ( e [ '<STR_LIT>' ] for u , v , e in R . edges ( data = True ) ) ) ) <EOL> if wmax == - inf : <EOL> return flow_cost , _build_flow_dict ( G , R , capacity , weight ) <EOL> R_node = R . node <EOL> R_succ = R . succ <EOL> delta = <NUM_LIT:2> ** int ( log ( wmax , <NUM_LIT:2> ) ) <EOL> while delta >= <NUM_LIT:1> : <EOL> for u in R : <EOL> p_u = R_node [ u ] [ '<STR_LIT>' ] <EOL> for v , es in R_succ [ u ] . items ( ) : <EOL> for k , e in es . items ( ) : <EOL> flow = e [ '<STR_LIT>' ] - e [ '<STR_LIT>' ] <EOL> if e [ '<STR_LIT>' ] - p_u + R_node [ v ] [ '<STR_LIT>' ] < <NUM_LIT:0> : <EOL> flow = e [ '<STR_LIT>' ] - e [ '<STR_LIT>' ] <EOL> if flow >= delta : <EOL> e [ '<STR_LIT>' ] += flow <EOL> R_succ [ v ] [ u ] [ ( k [ <NUM_LIT:0> ] , not k [ <NUM_LIT:1> ] ) ] [ '<STR_LIT>' ] -= flow <EOL> R_node [ u ] [ '<STR_LIT>' ] -= flow <EOL> R_node [ v ] [ '<STR_LIT>' ] += flow <EOL> S = set ( ) <EOL> T = set ( ) <EOL> S_add = S . add <EOL> S_remove = S . remove <EOL> T_add = T . add <EOL> T_remove = T . remove <EOL> for u in R : <EOL> excess = R_node [ u ] [ '<STR_LIT>' ] <EOL> if excess >= delta : <EOL> S_add ( u ) <EOL> elif excess <= - delta : <EOL> T_add ( u ) <EOL> while S and T : <EOL> s = arbitrary_element ( S ) <EOL> t = None <EOL> d = { } <EOL> pred = { s : None } <EOL> h = heap ( ) <EOL> h_insert = h . insert <EOL> h_get = h . get <EOL> h_insert ( s , <NUM_LIT:0> ) <EOL> while h : <EOL> u , d_u = h . pop ( ) <EOL> d [ u ] = d_u <EOL> if u in T : <EOL> t = u <EOL> break <EOL> p_u = R_node [ u ] [ '<STR_LIT>' ] <EOL> for v , es in R_succ [ u ] . items ( ) : <EOL> if v in d : <EOL> continue <EOL> wmin = inf <EOL> for k , e in es . items ( ) : <EOL> if e [ '<STR_LIT>' ] - e [ '<STR_LIT>' ] >= delta : <EOL> w = e [ '<STR_LIT>' ] <EOL> if w < wmin : <EOL> wmin = w <EOL> kmin = k <EOL> emin = e <EOL> if wmin == inf : <EOL> continue <EOL> d_v = d_u + wmin - p_u + R_node [ v ] [ '<STR_LIT>' ] <EOL> if h_insert ( v , d_v ) : <EOL> pred [ v ] = ( u , kmin , emin ) <EOL> if t is not None : <EOL> while u != s : <EOL> v = u <EOL> u , k , e = pred [ v ] <EOL> e [ '<STR_LIT>' ] += delta <EOL> R_succ [ v ] [ u ] [ ( k [ <NUM_LIT:0> ] , not k [ <NUM_LIT:1> ] ) ] [ '<STR_LIT>' ] -= delta <EOL> R_node [ s ] [ '<STR_LIT>' ] -= delta <EOL> R_node [ t ] [ '<STR_LIT>' ] += delta <EOL> if R_node [ s ] [ '<STR_LIT>' ] < delta : <EOL> S_remove ( s ) <EOL> if R_node [ t ] [ '<STR_LIT>' ] > - delta : <EOL> T_remove ( t ) <EOL> d_t = d [ t ] <EOL> for u , d_u in d . items ( ) : <EOL> R_node [ u ] [ '<STR_LIT>' ] -= d_u - d_t <EOL> else : <EOL> S_remove ( s ) <EOL> delta //= <NUM_LIT:2> <EOL> if any ( R . node [ u ] [ '<STR_LIT>' ] != <NUM_LIT:0> for u in R ) : <EOL> raise nx . NetworkXUnfeasible ( '<STR_LIT>' ) <EOL> for u in R : <EOL> for v , es in R_succ [ u ] . items ( ) : <EOL> for e in es . values ( ) : <EOL> flow = e [ '<STR_LIT>' ] <EOL> if flow > <NUM_LIT:0> : <EOL> flow_cost += flow * e [ '<STR_LIT>' ] <EOL> return flow_cost , _build_flow_dict ( G , R , capacity , weight ) </s>
