Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / dominating.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```"""Functions for computing dominating sets in a graph.""" ``` ```from itertools import chain ``` ```import networkx as nx ``` ```from networkx.utils import arbitrary_element ``` ```__author__ = '\n'.join(['Jordi Torrents ']) ``` ```__all__ = ['dominating_set', 'is_dominating_set'] ``` ```def dominating_set(G, start_with=None): ``` ``` r"""Finds a dominating set for the graph G. ``` ``` ``` ``` A *dominating set* for a graph with node set *V* is a subset *D* of ``` ``` *V* such that every node not in *D* is adjacent to at least one ``` ``` member of *D* _. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` start_with : node (default=None) ``` ``` Node to use as a starting point for the algorithm. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` D : set ``` ``` A dominating set for G. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` This function is an implementation of algorithm 7 in _ which ``` ``` finds some dominating set, not necessarily the smallest one. ``` ``` ``` ``` See also ``` ``` -------- ``` ``` is_dominating_set ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  https://en.wikipedia.org/wiki/Dominating_set ``` ``` ``` ``` ..  Abdol-Hossein Esfahanian. Connectivity Algorithms. ``` ``` http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf ``` ``` ``` ``` """ ``` ``` all_nodes = set(G) ``` ``` if start_with is None: ``` ``` start_with = arbitrary_element(all_nodes) ``` ``` if start_with not in G: ``` ``` raise nx.NetworkXError('node {} is not in G'.format(start_with)) ``` ``` dominating_set = {start_with} ``` ``` dominated_nodes = set(G[start_with]) ``` ``` remaining_nodes = all_nodes - dominated_nodes - dominating_set ``` ``` while remaining_nodes: ``` ``` # Choose an arbitrary node and determine its undominated neighbors. ``` ``` v = remaining_nodes.pop() ``` ``` undominated_neighbors = set(G[v]) - dominating_set ``` ``` # Add the node to the dominating set and the neighbors to the ``` ``` # dominated set. Finally, remove all of those nodes from the set ``` ``` # of remaining nodes. ``` ``` dominating_set.add(v) ``` ``` dominated_nodes |= undominated_neighbors ``` ``` remaining_nodes -= undominated_neighbors ``` ``` return dominating_set ``` ```def is_dominating_set(G, nbunch): ``` ``` """Checks if `nbunch` is a dominating set for `G`. ``` ``` ``` ``` A *dominating set* for a graph with node set *V* is a subset *D* of ``` ``` *V* such that every node not in *D* is adjacent to at least one ``` ``` member of *D* _. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` nbunch : iterable ``` ``` An iterable of nodes in the graph `G`. ``` ``` ``` ``` See also ``` ``` -------- ``` ``` dominating_set ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  https://en.wikipedia.org/wiki/Dominating_set ``` ``` ``` ``` """ ``` ``` testset = set(n for n in nbunch if n in G) ``` ``` nbrs = set(chain.from_iterable(G[n] for n in testset)) ``` ``` return len(set(G) - testset - nbrs) == 0 ```