Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/vertex_cover.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 computing an approximate minimum weight vertex cover. | |
2 | |
3 A |vertex cover|_ is a subset of nodes such that each edge in the graph | |
4 is incident to at least one node in the subset. | |
5 | |
6 .. _vertex cover: https://en.wikipedia.org/wiki/Vertex_cover | |
7 .. |vertex cover| replace:: *vertex cover* | |
8 | |
9 """ | |
10 | |
11 __all__ = ["min_weighted_vertex_cover"] | |
12 | |
13 | |
14 def min_weighted_vertex_cover(G, weight=None): | |
15 r"""Returns an approximate minimum weighted vertex cover. | |
16 | |
17 The set of nodes returned by this function is guaranteed to be a | |
18 vertex cover, and the total weight of the set is guaranteed to be at | |
19 most twice the total weight of the minimum weight vertex cover. In | |
20 other words, | |
21 | |
22 .. math:: | |
23 | |
24 w(S) \leq 2 * w(S^*), | |
25 | |
26 where $S$ is the vertex cover returned by this function, | |
27 $S^*$ is the vertex cover of minimum weight out of all vertex | |
28 covers of the graph, and $w$ is the function that computes the | |
29 sum of the weights of each node in that given set. | |
30 | |
31 Parameters | |
32 ---------- | |
33 G : NetworkX graph | |
34 | |
35 weight : string, optional (default = None) | |
36 If None, every node has weight 1. If a string, use this node | |
37 attribute as the node weight. A node without this attribute is | |
38 assumed to have weight 1. | |
39 | |
40 Returns | |
41 ------- | |
42 min_weighted_cover : set | |
43 Returns a set of nodes whose weight sum is no more than twice | |
44 the weight sum of the minimum weight vertex cover. | |
45 | |
46 Notes | |
47 ----- | |
48 For a directed graph, a vertex cover has the same definition: a set | |
49 of nodes such that each edge in the graph is incident to at least | |
50 one node in the set. Whether the node is the head or tail of the | |
51 directed edge is ignored. | |
52 | |
53 This is the local-ratio algorithm for computing an approximate | |
54 vertex cover. The algorithm greedily reduces the costs over edges, | |
55 iteratively building a cover. The worst-case runtime of this | |
56 implementation is $O(m \log n)$, where $n$ is the number | |
57 of nodes and $m$ the number of edges in the graph. | |
58 | |
59 References | |
60 ---------- | |
61 .. [1] Bar-Yehuda, R., and Even, S. (1985). "A local-ratio theorem for | |
62 approximating the weighted vertex cover problem." | |
63 *Annals of Discrete Mathematics*, 25, 27–46 | |
64 <http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdf> | |
65 | |
66 """ | |
67 cost = dict(G.nodes(data=weight, default=1)) | |
68 # While there are uncovered edges, choose an uncovered and update | |
69 # the cost of the remaining edges. | |
70 for u, v in G.edges(): | |
71 min_cost = min(cost[u], cost[v]) | |
72 cost[u] -= min_cost | |
73 cost[v] -= min_cost | |
74 return {u for u, c in cost.items() if c == 0} |