ioftools / networkxMiCe / networkxmaster / networkx / algorithms / dominating.py @ 5cef0f13
History  View  Annotate  Download (2.68 KB)
1 
# * coding: utf8 *


2 
"""Functions for computing dominating sets in a graph."""

3 
from itertools import chain 
4  
5 
import networkx as nx 
6 
from networkx.utils import arbitrary_element 
7  
8 
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>']) 
9 
__all__ = ['dominating_set', 'is_dominating_set'] 
10  
11  
12 
def dominating_set(G, start_with=None): 
13 
r"""Finds a dominating set for the graph G.

14 

15 
A *dominating set* for a graph with node set *V* is a subset *D* of

16 
*V* such that every node not in *D* is adjacent to at least one

17 
member of *D* [1]_.

18 

19 
Parameters

20 


21 
G : NetworkX graph

22 

23 
start_with : node (default=None)

24 
Node to use as a starting point for the algorithm.

25 

26 
Returns

27 


28 
D : set

29 
A dominating set for G.

30 

31 
Notes

32 


33 
This function is an implementation of algorithm 7 in [2]_ which

34 
finds some dominating set, not necessarily the smallest one.

35 

36 
See also

37 


38 
is_dominating_set

39 

40 
References

41 


42 
.. [1] https://en.wikipedia.org/wiki/Dominating_set

43 

44 
.. [2] AbdolHossein Esfahanian. Connectivity Algorithms.

45 
http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

46 

47 
"""

48 
all_nodes = set(G)

49 
if start_with is None: 
50 
start_with = arbitrary_element(all_nodes) 
51 
if start_with not in G: 
52 
raise nx.NetworkXError('node {} is not in G'.format(start_with)) 
53 
dominating_set = {start_with} 
54 
dominated_nodes = set(G[start_with])

55 
remaining_nodes = all_nodes  dominated_nodes  dominating_set 
56 
while remaining_nodes:

57 
# Choose an arbitrary node and determine its undominated neighbors.

58 
v = remaining_nodes.pop() 
59 
undominated_neighbors = set(G[v])  dominating_set

60 
# Add the node to the dominating set and the neighbors to the

61 
# dominated set. Finally, remove all of those nodes from the set

62 
# of remaining nodes.

63 
dominating_set.add(v) 
64 
dominated_nodes = undominated_neighbors 
65 
remaining_nodes = undominated_neighbors 
66 
return dominating_set

67  
68  
69 
def is_dominating_set(G, nbunch): 
70 
"""Checks if `nbunch` is a dominating set for `G`.

71 

72 
A *dominating set* for a graph with node set *V* is a subset *D* of

73 
*V* such that every node not in *D* is adjacent to at least one

74 
member of *D* [1]_.

75 

76 
Parameters

77 


78 
G : NetworkX graph

79 

80 
nbunch : iterable

81 
An iterable of nodes in the graph `G`.

82 

83 
See also

84 


85 
dominating_set

86 

87 
References

88 


89 
.. [1] https://en.wikipedia.org/wiki/Dominating_set

90 

91 
"""

92 
testset = set(n for n in nbunch if n in G) 
93 
nbrs = set(chain.from_iterable(G[n] for n in testset)) 
94 
return len(set(G)  testset  nbrs) == 0 