Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/dominating.py: 31%

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

2from itertools import chain 

3 

4import networkx as nx 

5from networkx.utils import arbitrary_element 

6 

7__all__ = ["dominating_set", "is_dominating_set"] 

8 

9 

10@nx._dispatch 

11def dominating_set(G, start_with=None): 

12 r"""Finds a dominating set for the graph G. 

13 

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

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

16 member of *D* [1]_. 

17 

18 Parameters 

19 ---------- 

20 G : NetworkX graph 

21 

22 start_with : node (default=None) 

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

24 

25 Returns 

26 ------- 

27 D : set 

28 A dominating set for G. 

29 

30 Notes 

31 ----- 

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

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

34 

35 See also 

36 -------- 

37 is_dominating_set 

38 

39 References 

40 ---------- 

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

42 

43 .. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms. 

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

45 

46 """ 

47 all_nodes = set(G) 

48 if start_with is None: 

49 start_with = arbitrary_element(all_nodes) 

50 if start_with not in G: 

51 raise nx.NetworkXError(f"node {start_with} is not in G") 

52 dominating_set = {start_with} 

53 dominated_nodes = set(G[start_with]) 

54 remaining_nodes = all_nodes - dominated_nodes - dominating_set 

55 while remaining_nodes: 

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

57 v = remaining_nodes.pop() 

58 undominated_neighbors = set(G[v]) - dominating_set 

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

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

61 # of remaining nodes. 

62 dominating_set.add(v) 

63 dominated_nodes |= undominated_neighbors 

64 remaining_nodes -= undominated_neighbors 

65 return dominating_set 

66 

67 

68@nx._dispatch 

69def 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 = {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