<s> """<STR_LIT>""" <EOL> import networkx as nx <EOL> __all__ = [ "<STR_LIT>" , <EOL> "<STR_LIT>" ] <EOL> __author__ = """<STR_LIT>""" <EOL> def min_weighted_dominating_set ( G , weight = None ) : <EOL> r"""<STR_LIT>""" <EOL> if not G : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> dom_set = set ( [ ] ) <EOL> cost_func = dict ( ( node , nd . get ( weight , <NUM_LIT:1> ) ) for node , nd in G . nodes_iter ( data = True ) ) <EOL> vertices = set ( G ) <EOL> sets = dict ( ( node , set ( [ node ] ) | set ( G [ node ] ) ) for node in G ) <EOL> def _cost ( subset ) : <EOL> """<STR_LIT>""" <EOL> cost = sum ( cost_func [ node ] for node in subset ) <EOL> return cost / float ( len ( subset - dom_set ) ) <EOL> while vertices : <EOL> dom_node , min_set = min ( sets . items ( ) , <EOL> key = lambda x : ( x [ <NUM_LIT:0> ] , _cost ( x [ <NUM_LIT:1> ] ) ) ) <EOL> alpha = _cost ( min_set ) <EOL> for node in min_set - dom_set : <EOL> cost_func [ node ] = alpha <EOL> dom_set . add ( dom_node ) <EOL> del sets [ dom_node ] <EOL> vertices = vertices - min_set <EOL> return dom_set <EOL> def min_edge_dominating_set ( G ) : <EOL> r"""<STR_LIT>""" <EOL> if not G : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> return nx . maximal_matching ( G ) </s>
