<s> """<STR_LIT>""" <EOL> __author__ = """<STR_LIT>""" <EOL> from collections import deque <EOL> import networkx as nx <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> class CurrentEdge ( object ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ) <EOL> def __init__ ( self , edges ) : <EOL> self . _edges = edges <EOL> if self . _edges : <EOL> self . _rewind ( ) <EOL> def get ( self ) : <EOL> return self . _curr <EOL> def move_to_next ( self ) : <EOL> try : <EOL> self . _curr = next ( self . _it ) <EOL> except StopIteration : <EOL> self . _rewind ( ) <EOL> raise <EOL> def _rewind ( self ) : <EOL> self . _it = iter ( self . _edges . items ( ) ) <EOL> self . _curr = next ( self . _it ) <EOL> class Level ( object ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = ( '<STR_LIT>' , '<STR_LIT>' ) <EOL> def __init__ ( self ) : <EOL> self . active = set ( ) <EOL> self . inactive = set ( ) <EOL> class GlobalRelabelThreshold ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , n , m , freq ) : <EOL> self . _threshold = ( n + m ) / freq if freq else float ( '<STR_LIT>' ) <EOL> self . _work = <NUM_LIT:0> <EOL> def add_work ( self , work ) : <EOL> self . _work += work <EOL> def is_reached ( self ) : <EOL> return self . _work >= self . _threshold <EOL> def clear_work ( self ) : <EOL> self . _work = <NUM_LIT:0> <EOL> def build_residual_network ( G , capacity ) : <EOL> """<STR_LIT>""" <EOL> if G . is_multigraph ( ) : <EOL> raise nx . NetworkXError ( <EOL> '<STR_LIT>' ) <EOL> R = nx . DiGraph ( ) <EOL> R . add_nodes_from ( G ) <EOL> inf = float ( '<STR_LIT>' ) <EOL> edge_list = [ ( u , v , attr ) for u , v , attr in G . edges ( data = True ) <EOL> if u != v and attr . get ( capacity , inf ) > <NUM_LIT:0> ] <EOL> inf = <NUM_LIT:3> * sum ( attr [ capacity ] for u , v , attr in edge_list <EOL> if capacity in attr and attr [ capacity ] != inf ) or <NUM_LIT:1> <EOL> if G . is_directed ( ) : <EOL> for u , v , attr in edge_list : <EOL> r = min ( attr . get ( capacity , inf ) , inf ) <EOL> if not R . has_edge ( u , v ) : <EOL> R . add_edge ( u , v , capacity = r ) <EOL> R . add_edge ( v , u , capacity = <NUM_LIT:0> ) <EOL> else : <EOL> R [ u ] [ v ] [ '<STR_LIT>' ] = r <EOL> else : <EOL> for u , v , attr in edge_list : <EOL> r = min ( attr . get ( capacity , inf ) , inf ) <EOL> R . add_edge ( u , v , capacity = r ) <EOL> R . add_edge ( v , u , capacity = r ) <EOL> R . graph [ '<STR_LIT>' ] = inf <EOL> return R <EOL> def detect_unboundedness ( R , s , t ) : <EOL> """<STR_LIT>""" <EOL> q = deque ( [ s ] ) <EOL> seen = set ( [ s ] ) <EOL> inf = R . graph [ '<STR_LIT>' ] <EOL> while q : <EOL> u = q . popleft ( ) <EOL> for v , attr in R [ u ] . items ( ) : <EOL> if attr [ '<STR_LIT>' ] == inf and v not in seen : <EOL> if v == t : <EOL> raise nx . NetworkXUnbounded ( <EOL> '<STR_LIT>' ) <EOL> seen . add ( v ) <EOL> q . append ( v ) <EOL> def build_flow_dict ( G , R ) : <EOL> """<STR_LIT>""" <EOL> flow_dict = { } <EOL> for u in G : <EOL> flow_dict [ u ] = dict ( ( v , <NUM_LIT:0> ) for v in G [ u ] ) <EOL> flow_dict [ u ] . update ( ( v , attr [ '<STR_LIT>' ] ) for v , attr in R [ u ] . items ( ) <EOL> if attr [ '<STR_LIT>' ] > <NUM_LIT:0> ) <EOL> return flow_dict </s>
