ioftools / networkxMiCe / networkxmaster / networkx / algorithms / approximation / vertex_cover.py @ 5cef0f13
History  View  Annotate  Download (2.77 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20112012 by

3 
# Nicholas Mancuso <nick.mancuso@gmail.com>

4 
# All rights reserved.

5 
# BSD license.

6 
#

7 
# Author:

8 
# Nicholas Mancuso <nick.mancuso@gmail.com>

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

10 

11 
A vertex cover_ is a subset of nodes such that each edge in the graph

12 
is incident to at least one node in the subset.

13 

14 
.. _vertex cover: https://en.wikipedia.org/wiki/Vertex_cover

15 
.. vertex cover replace:: *vertex cover*

16 

17 
"""

18  
19 
__all__ = ["min_weighted_vertex_cover"]

20  
21  
22 
def min_weighted_vertex_cover(G, weight=None): 
23 
r"""Returns an approximate minimum weighted vertex cover.

24 

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

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

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

28 
other words,

29 

30 
.. math::

31 

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

33 

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

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

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

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

38 

39 
Parameters

40 


41 
G : NetworkX graph

42 

43 
weight : string, optional (default = None)

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

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

46 
assumed to have weight 1.

47 

48 
Returns

49 


50 
min_weighted_cover : set

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

52 
the weight sum of the minimum weight vertex cover.

53 

54 
Notes

55 


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

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

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

59 
directed edge is ignored.

60 

61 
This is the localratio algorithm for computing an approximate

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

63 
iteratively building a cover. The worstcase runtime of this

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

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

66 

67 
References

68 


69 
.. [1] BarYehuda, R., and Even, S. (1985). "A localratio theorem for

70 
approximating the weighted vertex cover problem."

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

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

73 

74 
"""

75 
cost = dict(G.nodes(data=weight, default=1)) 
76 
# While there are uncovered edges, choose an uncovered and update

77 
# the cost of the remaining edges.

78 
for u, v in G.edges(): 
79 
min_cost = min(cost[u], cost[v])

80 
cost[u] = min_cost 
81 
cost[v] = min_cost 
82 
return {u for u, c in cost.items() if c == 0} 