### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/vertex_cover.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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 ..  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}