Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/dominating_set.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for finding node and edge dominating sets. | |
2 | |
3 A `dominating set`_ for an undirected graph *G* with vertex set *V* | |
4 and 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`_ | |
6 is a subset *F* of *E* such that every edge not in *F* is | |
7 incident to an endpoint of at least one edge in *F*. | |
8 | |
9 .. _dominating set: https://en.wikipedia.org/wiki/Dominating_set | |
10 .. _edge dominating set: https://en.wikipedia.org/wiki/Edge_dominating_set | |
11 | |
12 """ | |
13 | |
14 from ..matching import maximal_matching | |
15 from ...utils import not_implemented_for | |
16 | |
17 __all__ = ["min_weighted_dominating_set", "min_edge_dominating_set"] | |
18 | |
19 | |
20 # TODO Why doesn't this algorithm work for directed graphs? | |
21 @not_implemented_for("directed") | |
22 def min_weighted_dominating_set(G, weight=None): | |
23 r"""Returns a dominating set that approximates the minimum weight node | |
24 dominating set. | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : NetworkX graph | |
29 Undirected graph. | |
30 | |
31 weight : string | |
32 The node attribute storing the weight of an node. If provided, | |
33 the node attribute with this key must be a number for each | |
34 node. If not provided, each node is assumed to have weight one. | |
35 | |
36 Returns | |
37 ------- | |
38 min_weight_dominating_set : set | |
39 A set of nodes, the sum of whose weights is no more than `(\log | |
40 w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of | |
41 each node in the graph and `w(V^*)` denotes the sum of the | |
42 weights of each node in the minimum weight dominating set. | |
43 | |
44 Notes | |
45 ----- | |
46 This algorithm computes an approximate minimum weighted dominating | |
47 set for the graph `G`. The returned solution has weight `(\log | |
48 w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each | |
49 node in the graph and `w(V^*)` denotes the sum of the weights of | |
50 each node in the minimum weight dominating set for the graph. | |
51 | |
52 This implementation of the algorithm runs in $O(m)$ time, where $m$ | |
53 is the number of edges in the graph. | |
54 | |
55 References | |
56 ---------- | |
57 .. [1] Vazirani, Vijay V. | |
58 *Approximation Algorithms*. | |
59 Springer Science & Business Media, 2001. | |
60 | |
61 """ | |
62 # The unique dominating set for the null graph is the empty set. | |
63 if len(G) == 0: | |
64 return set() | |
65 | |
66 # This is the dominating set that will eventually be returned. | |
67 dom_set = set() | |
68 | |
69 def _cost(node_and_neighborhood): | |
70 """Returns the cost-effectiveness of greedily choosing the given | |
71 node. | |
72 | |
73 `node_and_neighborhood` is a two-tuple comprising a node and its | |
74 closed neighborhood. | |
75 | |
76 """ | |
77 v, neighborhood = node_and_neighborhood | |
78 return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set) | |
79 | |
80 # This is a set of all vertices not already covered by the | |
81 # dominating set. | |
82 vertices = set(G) | |
83 # This is a dictionary mapping each node to the closed neighborhood | |
84 # of that node. | |
85 neighborhoods = {v: {v} | set(G[v]) for v in G} | |
86 | |
87 # Continue until all vertices are adjacent to some node in the | |
88 # dominating set. | |
89 while vertices: | |
90 # Find the most cost-effective node to add, along with its | |
91 # closed neighborhood. | |
92 dom_node, min_set = min(neighborhoods.items(), key=_cost) | |
93 # Add the node to the dominating set and reduce the remaining | |
94 # set of nodes to cover. | |
95 dom_set.add(dom_node) | |
96 del neighborhoods[dom_node] | |
97 vertices -= min_set | |
98 | |
99 return dom_set | |
100 | |
101 | |
102 def min_edge_dominating_set(G): | |
103 r"""Returns minimum cardinality edge dominating set. | |
104 | |
105 Parameters | |
106 ---------- | |
107 G : NetworkX graph | |
108 Undirected graph | |
109 | |
110 Returns | |
111 ------- | |
112 min_edge_dominating_set : set | |
113 Returns a set of dominating edges whose size is no more than 2 * OPT. | |
114 | |
115 Notes | |
116 ----- | |
117 The algorithm computes an approximate solution to the edge dominating set | |
118 problem. The result is no more than 2 * OPT in terms of size of the set. | |
119 Runtime of the algorithm is $O(|E|)$. | |
120 """ | |
121 if not G: | |
122 raise ValueError("Expected non-empty NetworkX graph!") | |
123 return maximal_matching(G) |