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 finding node and edge dominating sets.
3A `dominating set`_ for an undirected graph *G* with vertex set *V*
4and edge set *E* is a subset *D* of *V* such that every vertex not in
5*D* is adjacent to at least one member of *D*. An `edge dominating set`_
6is a subset *F* of *E* such that every edge not in *F* is
7incident to an endpoint of at least one edge in *F*.
9.. _dominating set: https://en.wikipedia.org/wiki/Dominating_set
10.. _edge dominating set: https://en.wikipedia.org/wiki/Edge_dominating_set
12"""
14import networkx as nx
16from ...utils import not_implemented_for
17from ..matching import maximal_matching
19__all__ = ["min_weighted_dominating_set", "min_edge_dominating_set"]
22# TODO Why doesn't this algorithm work for directed graphs?
23@not_implemented_for("directed")
24@nx._dispatchable(node_attrs="weight")
25def min_weighted_dominating_set(G, weight=None):
26 r"""Returns a dominating set that approximates the minimum weight node
27 dominating set.
29 Parameters
30 ----------
31 G : NetworkX graph
32 Undirected graph.
34 weight : string
35 The node attribute storing the weight of an node. If provided,
36 the node attribute with this key must be a number for each
37 node. If not provided, each node is assumed to have weight one.
39 Returns
40 -------
41 min_weight_dominating_set : set
42 A set of nodes, the sum of whose weights is no more than `(\log
43 w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of
44 each node in the graph and `w(V^*)` denotes the sum of the
45 weights of each node in the minimum weight dominating set.
47 Examples
48 --------
49 >>> G = nx.Graph([(0, 1), (0, 4), (1, 4), (1, 2), (2, 3), (3, 4), (2, 5)])
50 >>> nx.approximation.min_weighted_dominating_set(G)
51 {1, 2, 4}
53 Raises
54 ------
55 NetworkXNotImplemented
56 If G is directed.
58 Notes
59 -----
60 This algorithm computes an approximate minimum weighted dominating
61 set for the graph `G`. The returned solution has weight `(\log
62 w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each
63 node in the graph and `w(V^*)` denotes the sum of the weights of
64 each node in the minimum weight dominating set for the graph.
66 This implementation of the algorithm runs in $O(m)$ time, where $m$
67 is the number of edges in the graph.
69 References
70 ----------
71 .. [1] Vazirani, Vijay V.
72 *Approximation Algorithms*.
73 Springer Science & Business Media, 2001.
75 """
76 # The unique dominating set for the null graph is the empty set.
77 if len(G) == 0:
78 return set()
80 # This is the dominating set that will eventually be returned.
81 dom_set = set()
83 def _cost(node_and_neighborhood):
84 """Returns the cost-effectiveness of greedily choosing the given
85 node.
87 `node_and_neighborhood` is a two-tuple comprising a node and its
88 closed neighborhood.
90 """
91 v, neighborhood = node_and_neighborhood
92 return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)
94 # This is a set of all vertices not already covered by the
95 # dominating set.
96 vertices = set(G)
97 # This is a dictionary mapping each node to the closed neighborhood
98 # of that node.
99 neighborhoods = {v: {v} | set(G[v]) for v in G}
101 # Continue until all vertices are adjacent to some node in the
102 # dominating set.
103 while vertices:
104 # Find the most cost-effective node to add, along with its
105 # closed neighborhood.
106 dom_node, min_set = min(neighborhoods.items(), key=_cost)
107 # Add the node to the dominating set and reduce the remaining
108 # set of nodes to cover.
109 dom_set.add(dom_node)
110 del neighborhoods[dom_node]
111 vertices -= min_set
113 return dom_set
116@nx._dispatchable
117def min_edge_dominating_set(G):
118 r"""Returns minimum cardinality edge dominating set.
120 Parameters
121 ----------
122 G : NetworkX graph
123 Undirected graph
125 Returns
126 -------
127 min_edge_dominating_set : set
128 Returns a set of dominating edges whose size is no more than 2 * OPT.
130 Examples
131 --------
132 >>> G = nx.petersen_graph()
133 >>> nx.approximation.min_edge_dominating_set(G)
134 {(0, 1), (4, 9), (6, 8), (5, 7), (2, 3)}
136 Raises
137 ------
138 ValueError
139 If the input graph `G` is empty.
141 Notes
142 -----
143 The algorithm computes an approximate solution to the edge dominating set
144 problem. The result is no more than 2 * OPT in terms of size of the set.
145 Runtime of the algorithm is $O(|E|)$.
146 """
147 if not G:
148 raise ValueError("Expected non-empty NetworkX graph!")
149 return maximal_matching(G)