Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for computing dominating sets in a graph."""
3import math
4from heapq import heappop, heappush
5from itertools import chain, count
7import networkx as nx
9__all__ = [
10 "dominating_set",
11 "is_dominating_set",
12 "connected_dominating_set",
13 "is_connected_dominating_set",
14]
17@nx._dispatchable
18def dominating_set(G, start_with=None):
19 r"""Finds a dominating set for the graph G.
21 A *dominating set* for a graph with node set *V* is a subset *D* of
22 *V* such that every node not in *D* is adjacent to at least one
23 member of *D* [1]_.
25 Parameters
26 ----------
27 G : NetworkX graph
29 start_with : node (default=None)
30 Node to use as a starting point for the algorithm.
32 Returns
33 -------
34 D : set
35 A dominating set for G.
37 Notes
38 -----
39 This function is an implementation of algorithm 7 in [2]_ which
40 finds some dominating set, not necessarily the smallest one.
42 See also
43 --------
44 is_dominating_set
46 References
47 ----------
48 .. [1] https://en.wikipedia.org/wiki/Dominating_set
50 .. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms.
51 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
53 """
54 all_nodes = set(G)
55 if start_with is None:
56 start_with = nx.utils.arbitrary_element(all_nodes)
57 if start_with not in G:
58 raise nx.NetworkXError(f"node {start_with} is not in G")
59 dominating_set = {start_with}
60 dominated_nodes = set(G[start_with])
61 remaining_nodes = all_nodes - dominated_nodes - dominating_set
62 while remaining_nodes:
63 # Choose an arbitrary node and determine its undominated neighbors.
64 v = remaining_nodes.pop()
65 undominated_nbrs = set(G[v]) - dominating_set
66 # Add the node to the dominating set and the neighbors to the
67 # dominated set. Finally, remove all of those nodes from the set
68 # of remaining nodes.
69 dominating_set.add(v)
70 dominated_nodes |= undominated_nbrs
71 remaining_nodes -= undominated_nbrs
72 return dominating_set
75@nx._dispatchable
76def is_dominating_set(G, nbunch):
77 """Checks if `nbunch` is a dominating set for `G`.
79 A *dominating set* for a graph with node set *V* is a subset *D* of
80 *V* such that every node not in *D* is adjacent to at least one
81 member of *D* [1]_.
83 Parameters
84 ----------
85 G : NetworkX graph
87 nbunch : iterable
88 An iterable of nodes in the graph `G`.
90 Returns
91 -------
92 dominating : bool
93 True if `nbunch` is a dominating set of `G`, false otherwise.
95 See also
96 --------
97 dominating_set
99 References
100 ----------
101 .. [1] https://en.wikipedia.org/wiki/Dominating_set
103 """
104 testset = {n for n in nbunch if n in G}
105 nbrs = set(chain.from_iterable(G[n] for n in testset))
106 return len(set(G) - testset - nbrs) == 0
109@nx.utils.not_implemented_for("directed")
110@nx._dispatchable
111def connected_dominating_set(G):
112 """Returns a connected dominating set.
114 A *dominating set* for a graph *G* with node set *V* is a subset *D* of *V*
115 such that every node not in *D* is adjacent to at least one member of *D*
116 [1]_. A *connected dominating set* is a dominating set *C* that induces a
117 connected subgraph of *G* [2]_.
118 Note that connected dominating sets are not unique in general and that there
119 may be other connected dominating sets.
121 Parameters
122 ----------
123 G : NewtorkX graph
124 Undirected connected graph.
126 Returns
127 -------
128 connected_dominating_set : set
129 A dominating set of nodes which induces a connected subgraph of G.
131 Raises
132 ------
133 NetworkXNotImplemented
134 If G is directed.
136 NetworkXError
137 If G is disconnected.
139 Examples
140 ________
141 >>> G = nx.Graph(
142 ... [
143 ... (1, 2),
144 ... (1, 3),
145 ... (1, 4),
146 ... (1, 5),
147 ... (1, 6),
148 ... (2, 7),
149 ... (3, 8),
150 ... (4, 9),
151 ... (5, 10),
152 ... (6, 11),
153 ... (7, 12),
154 ... (8, 12),
155 ... (9, 12),
156 ... (10, 12),
157 ... (11, 12),
158 ... ]
159 ... )
160 >>> nx.connected_dominating_set(G)
161 {1, 2, 3, 4, 5, 6, 7}
163 Notes
164 -----
165 This function implements Algorithm I in its basic version as described
166 in [3]_. The idea behind the algorithm is the following: grow a tree *T*,
167 starting from a node with maximum degree. Throughout the growing process,
168 nonleaf nodes in *T* are our connected dominating set (CDS), leaf nodes in
169 *T* are marked as "seen" and nodes in G that are not yet in *T* are marked as
170 "unseen". We maintain a max-heap of all "seen" nodes, and track the number
171 of "unseen" neighbors for each node. At each step we pop the heap top -- a
172 "seen" (leaf) node with maximal number of "unseen" neighbors, add it to the
173 CDS and mark all its "unseen" neighbors as "seen". For each one of the newly
174 created "seen" nodes, we also decrement the number of "unseen" neighbors for
175 all its neighbors. The algorithm terminates when there are no more "unseen"
176 nodes.
177 Runtime complexity of this implementation is $O(|E|*log|V|)$ (amortized).
179 References
180 ----------
181 .. [1] https://en.wikipedia.org/wiki/Dominating_set
182 .. [2] https://en.wikipedia.org/wiki/Connected_dominating_set
183 .. [3] Guha, S. and Khuller, S.
184 *Approximation Algorithms for Connected Dominating Sets*,
185 Algorithmica, 20, 374-387, 1998.
187 """
188 if len(G) == 0:
189 return set()
191 if not nx.is_connected(G):
192 raise nx.NetworkXError("G must be a connected graph")
194 if len(G) == 1:
195 return set(G)
197 G_succ = G._adj # For speed-up
199 # Use the count c to avoid comparing nodes
200 c = count()
202 # Keep track of the number of unseen nodes adjacent to each node
203 unseen_degree = dict(G.degree)
205 # Find node with highest degree and update its neighbors
206 (max_deg_node, max_deg) = max(unseen_degree.items(), key=lambda x: x[1])
207 for nbr in G_succ[max_deg_node]:
208 unseen_degree[nbr] -= 1
210 # Initially all nodes except max_deg_node are unseen
211 unseen = set(G) - {max_deg_node}
213 # We want a max-heap of the unseen-degree using heapq, which is a min-heap
214 # So we store the negative of the unseen-degree
215 seen = [(-max_deg, next(c), max_deg_node)]
217 connected_dominating_set = set()
219 # Main loop
220 while unseen:
221 (neg_deg, cnt, u) = heappop(seen)
222 # Check if u's unseen-degree changed while in the heap
223 if -neg_deg > unseen_degree[u]:
224 heappush(seen, (-unseen_degree[u], cnt, u))
225 continue
226 # Mark all u's unseen neighbors as seen and add them to the heap
227 for v in G_succ[u]:
228 if v in unseen:
229 unseen.remove(v)
230 for nbr in G_succ[v]:
231 unseen_degree[nbr] -= 1
232 heappush(seen, (-unseen_degree[v], next(c), v))
233 # Add u to the dominating set
234 connected_dominating_set.add(u)
236 return connected_dominating_set
239@nx.utils.not_implemented_for("directed")
240@nx._dispatchable
241def is_connected_dominating_set(G, nbunch):
242 """Checks if `nbunch` is a connected dominating set for `G`.
244 A *dominating set* for a graph *G* with node set *V* is a subset *D* of
245 *V* such that every node not in *D* is adjacent to at least one
246 member of *D* [1]_. A *connected dominating set* is a dominating
247 set *C* that induces a connected subgraph of *G* [2]_.
249 Parameters
250 ----------
251 G : NetworkX graph
252 Undirected graph.
254 nbunch : iterable
255 An iterable of nodes in the graph `G`.
257 Returns
258 -------
259 connected_dominating : bool
260 True if `nbunch` is connected dominating set of `G`, false otherwise.
262 References
263 ----------
264 .. [1] https://en.wikipedia.org/wiki/Dominating_set
265 .. [2] https://en.wikipedia.org/wiki/Connected_dominating_set
267 """
268 return nx.is_dominating_set(G, nbunch) and nx.is_connected(nx.subgraph(G, nbunch))