@not_implemented_for('directed')
def min_weighted_dominating_set(G, weight=None):
 if (len(G) == 0):
  return set()
 dom_set = set()
 def _cost(node_and_neighborhood):
  'Returns the cost-effectiveness of greedily choosing the given\n        node.\n\n        `node_and_neighborhood` is a two-tuple comprising a node and its\n        closed neighborhood.\n\n        '
  (v, neighborhood) = node_and_neighborhood
  return (G.node[v].get(weight, 1) / len((neighborhood - dom_set)))
 vertices = set(G)
 neighborhoods = {v: ({v} | set(G[v])) for v in G}
 while vertices:
  (dom_node, min_set) = min(neighborhoods.items(), key=_cost)
  dom_set.add(dom_node)
  del neighborhoods[dom_node]
  vertices -= min_set
 return dom_set

@ not_implemented_for ( 'directed' ) def min_weighted_dominating_set ( G , weight = None ) : if ( len ( G ) == 0 ) : return set ( ) dom_set = set ( ) def _cost ( node_and_neighborhood ) : ( v , neighborhood ) = node_and_neighborhood return ( G . node [ v ] . get ( weight , 1 ) / len ( ( neighborhood - dom_set ) ) ) vertices = set ( G ) neighborhoods = { v : ( { v } | set ( G [ v ] ) ) for v in G } while vertices : ( dom_node , min_set ) = min ( neighborhoods . items ( ) , key = _cost ) dom_set . add ( dom_node ) del neighborhoods [ dom_node ] vertices -= min_set return dom_set
returns a dominating set that approximates the minimum weight node dominating set .