Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/vertex_cover.py: 27%

1"""Functions for computing an approximate minimum weight vertex cover. 

2 

3A |vertex cover|_ is a subset of nodes such that each edge in the graph 

4is 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""" 

10import networkx as nx 

11 

12__all__ = ["min_weighted_vertex_cover"] 

13 

14 

15@nx._dispatch(node_attrs="weight") 

16def min_weighted_vertex_cover(G, weight=None): 

17 r"""Returns an approximate minimum weighted vertex cover. 

18 

19 The set of nodes returned by this function is guaranteed to be a 

20 vertex cover, and the total weight of the set is guaranteed to be at 

21 most twice the total weight of the minimum weight vertex cover. In 

22 other words, 

23 

24 .. math:: 

25 

26 w(S) \leq 2 * w(S^*), 

27 

28 where $S$ is the vertex cover returned by this function, 

29 $S^*$ is the vertex cover of minimum weight out of all vertex 

30 covers of the graph, and $w$ is the function that computes the 

31 sum of the weights of each node in that given set. 

32 

33 Parameters 

34 ---------- 

35 G : NetworkX graph 

36 

37 weight : string, optional (default = None) 

38 If None, every node has weight 1. If a string, use this node 

39 attribute as the node weight. A node without this attribute is 

40 assumed to have weight 1. 

41 

42 Returns 

43 ------- 

44 min_weighted_cover : set 

45 Returns a set of nodes whose weight sum is no more than twice 

46 the weight sum of the minimum weight vertex cover. 

47 

48 Notes 

49 ----- 

50 For a directed graph, a vertex cover has the same definition: a set 

51 of nodes such that each edge in the graph is incident to at least 

52 one node in the set. Whether the node is the head or tail of the 

53 directed edge is ignored. 

54 

55 This is the local-ratio algorithm for computing an approximate 

56 vertex cover. The algorithm greedily reduces the costs over edges, 

57 iteratively building a cover. The worst-case runtime of this 

58 implementation is $O(m \log n)$, where $n$ is the number 

59 of nodes and $m$ the number of edges in the graph. 

60 

61 References 

62 ---------- 

63 .. [1] Bar-Yehuda, R., and Even, S. (1985). "A local-ratio theorem for 

64 approximating the weighted vertex cover problem." 

65 *Annals of Discrete Mathematics*, 25, 27–46 

66 <http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdf> 

67 

68 """ 

69 cost = dict(G.nodes(data=weight, default=1)) 

70 # While there are uncovered edges, choose an uncovered and update 

71 # the cost of the remaining edges. 

72 cover = set() 

73 for u, v in G.edges(): 

74 if u in cover or v in cover: 

75 continue 

76 if cost[u] <= cost[v]: 

77 cover.add(u) 

78 cost[v] -= cost[u] 

79 else: 

80 cover.add(v) 

81 cost[u] -= cost[v] 

82 return cover