## Mercurial > repos > shellac > sam_consensus_v3

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

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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} |