<s> """<STR_LIT>""" <EOL> import itertools <EOL> from operator import itemgetter <EOL> import networkx as nx <EOL> from networkx . algorithms . connectivity . connectivity import _aux_digraph_node_connectivity , _aux_digraph_edge_connectivity , dominating_set , node_connectivity <EOL> __author__ = '<STR_LIT:\n>' . join ( [ '<STR_LIT>' ] ) <EOL> __all__ = [ '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> ] <EOL> def minimum_st_edge_cut ( G , s , t , capacity = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> flow , H = nx . ford_fulkerson_flow_and_auxiliary ( G , s , t , capacity = capacity ) <EOL> cutset = set ( ) <EOL> reachable = set ( nx . single_source_shortest_path ( H , s ) ) <EOL> others = set ( H ) - reachable <EOL> for u , nbrs in ( ( n , G [ n ] ) for n in reachable ) : <EOL> cutset . update ( ( u , v ) for v in nbrs if v in others ) <EOL> return cutset <EOL> except nx . NetworkXUnbounded : <EOL> raise nx . NetworkXUnbounded ( "<STR_LIT>" ) <EOL> def minimum_st_node_cut ( G , s , t , aux_digraph = None , mapping = None ) : <EOL> r"""<STR_LIT>""" <EOL> if aux_digraph is None or mapping is None : <EOL> H , mapping = _aux_digraph_node_connectivity ( G ) <EOL> else : <EOL> H = aux_digraph <EOL> edge_cut = minimum_st_edge_cut ( H , '<STR_LIT>' % mapping [ s ] , '<STR_LIT>' % mapping [ t ] ) <EOL> node_cut = set ( H . node [ node ] [ '<STR_LIT:id>' ] for edge in edge_cut for node in edge ) <EOL> return node_cut - set ( [ s , t ] ) <EOL> def minimum_node_cut ( G , s = None , t = None ) : <EOL> r"""<STR_LIT>""" <EOL> if s is not None and t is not None : <EOL> if s not in G : <EOL> raise nx . NetworkXError ( '<STR_LIT>' % s ) <EOL> if t not in G : <EOL> raise nx . NetworkXError ( '<STR_LIT>' % t ) <EOL> return minimum_st_node_cut ( G , s , t ) <EOL> if G . is_directed ( ) : <EOL> if not nx . is_weakly_connected ( G ) : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> iter_func = itertools . permutations <EOL> def neighbors ( v ) : <EOL> return itertools . chain . from_iterable ( [ G . predecessors_iter ( v ) , <EOL> G . successors_iter ( v ) ] ) <EOL> else : <EOL> if not nx . is_connected ( G ) : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> iter_func = itertools . combinations <EOL> neighbors = G . neighbors_iter <EOL> deg = G . degree ( ) <EOL> min_deg = min ( deg . values ( ) ) <EOL> v = next ( n for n , d in deg . items ( ) if d == min_deg ) <EOL> min_cut = set ( G [ v ] ) <EOL> H , mapping = _aux_digraph_node_connectivity ( G ) <EOL> for w in set ( G ) - set ( neighbors ( v ) ) - set ( [ v ] ) : <EOL> this_cut = minimum_st_node_cut ( G , v , w , aux_digraph = H , mapping = mapping ) <EOL> if len ( min_cut ) >= len ( this_cut ) : <EOL> min_cut = this_cut <EOL> for x , y in iter_func ( neighbors ( v ) , <NUM_LIT:2> ) : <EOL> if y in G [ x ] : continue <EOL> this_cut = minimum_st_node_cut ( G , x , y , aux_digraph = H , mapping = mapping ) <EOL> if len ( min_cut ) >= len ( this_cut ) : <EOL> min_cut = this_cut <EOL> return min_cut <EOL> def minimum_edge_cut ( G , s = None , t = None ) : <EOL> r"""<STR_LIT>""" <EOL> H = _aux_digraph_edge_connectivity ( G ) <EOL> if s is not None and t is not None : <EOL> if s not in G : <EOL> raise nx . NetworkXError ( '<STR_LIT>' % s ) <EOL> if t not in G : <EOL> raise nx . NetworkXError ( '<STR_LIT>' % t ) <EOL> return minimum_st_edge_cut ( H , s , t ) <EOL> if G . is_directed ( ) : <EOL> if not nx . is_weakly_connected ( G ) : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> deg = G . degree ( ) <EOL> min_deg = min ( deg . values ( ) ) <EOL> node = next ( n for n , d in deg . items ( ) if d == min_deg ) <EOL> min_cut = G . edges ( node ) <EOL> nodes = G . nodes ( ) <EOL> n = len ( nodes ) <EOL> for i in range ( n ) : <EOL> try : <EOL> this_cut = minimum_st_edge_cut ( H , nodes [ i ] , nodes [ i + <NUM_LIT:1> ] ) <EOL> if len ( this_cut ) <= len ( min_cut ) : <EOL> min_cut = this_cut <EOL> except IndexError : <EOL> this_cut = minimum_st_edge_cut ( H , nodes [ i ] , nodes [ <NUM_LIT:0> ] ) <EOL> if len ( this_cut ) <= len ( min_cut ) : <EOL> min_cut = this_cut <EOL> return min_cut <EOL> else : <EOL> if not nx . is_connected ( G ) : <EOL> raise nx . NetworkXError ( '<STR_LIT>' ) <EOL> deg = G . degree ( ) <EOL> min_deg = min ( deg . values ( ) ) <EOL> node = next ( n for n , d in deg . items ( ) if d == min_deg ) <EOL> min_cut = G . edges ( node ) <EOL> for node in G : <EOL> D = dominating_set ( G , start_with = node ) <EOL> v = D . pop ( ) <EOL> if D : break <EOL> else : <EOL> return min_cut <EOL> for w in D : <EOL> this_cut = minimum_st_edge_cut ( H , v , w ) <EOL> if len ( this_cut ) <= len ( min_cut ) : <EOL> min_cut = this_cut <EOL> return min_cut </s>
