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

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