#NEWLINE# def dominating_set( G , start_with = None ) : #NEWLINE# #INDENT# 'Finds a dominating set for the graph G.\n\n    A *dominating set* for a graph with node set *V* is a subset *D* of\n    *V* such that every node not in *D* is adjacent to at least one\n    member of *D* [1]_.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    start_with : node (default=None)\n        Node to use as a starting point for the algorithm.\n\n    Returns\n    -------\n    D : set\n        A dominating set for G.\n\n    Notes\n    -----\n    This function is an implementation of algorithm 7 in [2]_ which\n    finds some dominating set, not necessarily the smallest one.\n\n    See also\n    --------\n    is_dominating_set\n\n    References\n    ----------\n    .. [1] http://en.wikipedia.org/wiki/Dominating_set\n\n    .. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms.\n        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf\n\n    ' #NEWLINE# all_nodes = set ( G ) #NEWLINE# if ( start_with is None ) : #NEWLINE# #INDENT# start_with = arbitrary_element ( all_nodes ) #NEWLINE# #UNINDENT# if ( start_with not in G ) : #NEWLINE# #INDENT# raise nx . NetworkXError ( 'node {} is not in G' . format ( start_with ) ) #NEWLINE# #UNINDENT# dominating_set = { start_with } #NEWLINE# dominated_nodes = set ( G [ start_with ] ) #NEWLINE# remaining_nodes = ( ( all_nodes - dominated_nodes ) - dominating_set ) #NEWLINE# while remaining_nodes : #NEWLINE# #INDENT# v = remaining_nodes . pop ( ) #NEWLINE# undominated_neighbors = ( set ( G [ v ] ) - dominating_set ) #NEWLINE# dominating_set . add ( v ) #NEWLINE# dominated_nodes |= undominated_neighbors #NEWLINE# remaining_nodes -= undominated_neighbors #NEWLINE# #UNINDENT# return dominating_set