Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/dominating_set.py: 35%
26 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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"""
13import networkx as nx
15from ...utils import not_implemented_for
16from ..matching import maximal_matching
18__all__ = ["min_weighted_dominating_set", "min_edge_dominating_set"]
21# TODO Why doesn't this algorithm work for directed graphs?
22@not_implemented_for("directed")
23@nx._dispatch(node_attrs="weight")
24def min_weighted_dominating_set(G, weight=None):
25 r"""Returns a dominating set that approximates the minimum weight node
26 dominating set.
28 Parameters
29 ----------
30 G : NetworkX graph
31 Undirected graph.
33 weight : string
34 The node attribute storing the weight of an node. If provided,
35 the node attribute with this key must be a number for each
36 node. If not provided, each node is assumed to have weight one.
38 Returns
39 -------
40 min_weight_dominating_set : set
41 A set of nodes, the sum of whose weights is no more than `(\log
42 w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of
43 each node in the graph and `w(V^*)` denotes the sum of the
44 weights of each node in the minimum weight dominating set.
46 Notes
47 -----
48 This algorithm computes an approximate minimum weighted dominating
49 set for the graph `G`. The returned solution has weight `(\log
50 w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each
51 node in the graph and `w(V^*)` denotes the sum of the weights of
52 each node in the minimum weight dominating set for the graph.
54 This implementation of the algorithm runs in $O(m)$ time, where $m$
55 is the number of edges in the graph.
57 References
58 ----------
59 .. [1] Vazirani, Vijay V.
60 *Approximation Algorithms*.
61 Springer Science & Business Media, 2001.
63 """
64 # The unique dominating set for the null graph is the empty set.
65 if len(G) == 0:
66 return set()
68 # This is the dominating set that will eventually be returned.
69 dom_set = set()
71 def _cost(node_and_neighborhood):
72 """Returns the cost-effectiveness of greedily choosing the given
73 node.
75 `node_and_neighborhood` is a two-tuple comprising a node and its
76 closed neighborhood.
78 """
79 v, neighborhood = node_and_neighborhood
80 return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)
82 # This is a set of all vertices not already covered by the
83 # dominating set.
84 vertices = set(G)
85 # This is a dictionary mapping each node to the closed neighborhood
86 # of that node.
87 neighborhoods = {v: {v} | set(G[v]) for v in G}
89 # Continue until all vertices are adjacent to some node in the
90 # dominating set.
91 while vertices:
92 # Find the most cost-effective node to add, along with its
93 # closed neighborhood.
94 dom_node, min_set = min(neighborhoods.items(), key=_cost)
95 # Add the node to the dominating set and reduce the remaining
96 # set of nodes to cover.
97 dom_set.add(dom_node)
98 del neighborhoods[dom_node]
99 vertices -= min_set
101 return dom_set
104@nx._dispatch
105def min_edge_dominating_set(G):
106 r"""Returns minimum cardinality edge dominating set.
108 Parameters
109 ----------
110 G : NetworkX graph
111 Undirected graph
113 Returns
114 -------
115 min_edge_dominating_set : set
116 Returns a set of dominating edges whose size is no more than 2 * OPT.
118 Notes
119 -----
120 The algorithm computes an approximate solution to the edge dominating set
121 problem. The result is no more than 2 * OPT in terms of size of the set.
122 Runtime of the algorithm is $O(|E|)$.
123 """
124 if not G:
125 raise ValueError("Expected non-empty NetworkX graph!")
126 return maximal_matching(G)