<s> """<STR_LIT>""" <EOL> from itertools import islice <EOL> import networkx as nx <EOL> from ... utils import BinaryHeap <EOL> from ... utils import not_implemented_for <EOL> from ... utils import arbitrary_element <EOL> __author__ = '<STR_LIT>' <EOL> __all__ = [ '<STR_LIT>' ] <EOL> @ not_implemented_for ( '<STR_LIT>' ) <EOL> @ not_implemented_for ( '<STR_LIT>' ) <EOL> def stoer_wagner ( G , weight = '<STR_LIT>' , heap = BinaryHeap ) : <EOL> """<STR_LIT>""" <EOL> n = len ( G ) <EOL> if n < <NUM_LIT:2> : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> if not nx . is_connected ( G ) : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> G = nx . Graph ( ( u , v , { '<STR_LIT>' : e . get ( weight , <NUM_LIT:1> ) } ) <EOL> for u , v , e in G . edges ( data = True ) if u != v ) <EOL> for u , v , e , in G . edges ( data = True ) : <EOL> if e [ '<STR_LIT>' ] < <NUM_LIT:0> : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> cut_value = float ( '<STR_LIT>' ) <EOL> nodes = set ( G ) <EOL> contractions = [ ] <EOL> for i in range ( n - <NUM_LIT:1> ) : <EOL> u = arbitrary_element ( G ) <EOL> A = set ( [ u ] ) <EOL> h = heap ( ) <EOL> for v , e in G [ u ] . items ( ) : <EOL> h . insert ( v , - e [ '<STR_LIT>' ] ) <EOL> for j in range ( n - i - <NUM_LIT:2> ) : <EOL> u = h . pop ( ) [ <NUM_LIT:0> ] <EOL> A . add ( u ) <EOL> for v , e , in G [ u ] . items ( ) : <EOL> if v not in A : <EOL> h . insert ( v , h . get ( v , <NUM_LIT:0> ) - e [ '<STR_LIT>' ] ) <EOL> v , w = h . min ( ) <EOL> w = - w <EOL> if w < cut_value : <EOL> cut_value = w <EOL> best_phase = i <EOL> contractions . append ( ( u , v ) ) <EOL> for w , e in G [ v ] . items ( ) : <EOL> if w != u : <EOL> if w not in G [ u ] : <EOL> G . add_edge ( u , w , weight = e [ '<STR_LIT>' ] ) <EOL> else : <EOL> G [ u ] [ w ] [ '<STR_LIT>' ] += e [ '<STR_LIT>' ] <EOL> G . remove_node ( v ) <EOL> G = nx . Graph ( islice ( contractions , best_phase ) ) <EOL> v = contractions [ best_phase ] [ <NUM_LIT:1> ] <EOL> G . add_node ( v ) <EOL> reachable = set ( n for n , d in nx . single_source_shortest_path_length ( G , v ) ) <EOL> partition = ( list ( reachable ) , list ( nodes - reachable ) ) <EOL> return cut_value , partition </s>
