Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / vertex_cover.py @ 5cef0f13

History | View | Annotate | Download (2.77 KB)

1
# -*- coding: utf-8 -*-
2
#   Copyright (C) 2011-2012 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 local-ratio algorithm for computing an approximate
62
    vertex cover. The algorithm greedily reduces the costs over edges,
63
    iteratively building a cover. The worst-case 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] Bar-Yehuda, R., and Even, S. (1985). "A local-ratio 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}