Source code for networkx.algorithms.approximation.vertex_cover

"""用于计算近似最小权重顶点覆盖的函数。

*顶点覆盖* 是节点的一个子集，使得图中的每条边都至少与该子集中的一个节点相连。

.. _顶点覆盖: https://en.wikipedia.org/wiki/Vertex_cover
.. |顶点覆盖| replace:: *顶点覆盖*

"""

import networkx as nx

__all__ = ["min_weighted_vertex_cover"]




@nx._dispatchable(node_attrs="weight")
def min_weighted_vertex_cover(G, weight=None):
    r"""返回一个近似的最小加权顶点覆盖。

此函数返回的节点集合保证是一个顶点覆盖，并且该集合的总权重保证不超过最小权重顶点覆盖的总权重的两倍。换句话说，

.. math::

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

其中 $S$ 是此函数返回的顶点覆盖，$S^*$ 是图中所有顶点覆盖中权重最小的顶点覆盖，$w$ 是计算给定集合中每个节点权重和的函数。

Parameters
----------
G : NetworkX 图

weight : 字符串, 可选 (默认 = None)
    如果为 None，则每个节点的权重为 1。如果为字符串，则使用此节点属性作为节点权重。没有此属性的节点被假定权重为 1。

Returns
-------
min_weighted_cover : 集合
    返回一个节点集合，其权重和不超过最小权重顶点覆盖的权重和的两倍。

Notes
-----
对于有向图，顶点覆盖的定义相同：一个节点集合，使得图中的每条边至少与集合中的一个节点相邻。无论该节点是有向边的头部还是尾部，都被忽略。

这是用于计算近似顶点覆盖的局部比率算法。该算法贪婪地减少边上的成本，迭代地构建覆盖。此实现的最坏情况运行时间为 $O(m \log n)$，其中 $n$ 是节点数，$m$ 是图中的边数。

References
----------
.. [1] Bar-Yehuda, R., and Even, S. (1985). "A local-ratio theorem for approximating the weighted vertex cover problem."
   *Annals of Discrete Mathematics*, 25, 27–46
   <http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdf>
"""
    cost = dict(G.nodes(data=weight, default=1))
    # While there are uncovered edges, choose an uncovered and update
    # the cost of the remaining edges.
    cover = set()
    for u, v in G.edges():
        if u in cover or v in cover:
            continue
        if cost[u] <= cost[v]:
            cover.add(u)
            cost[v] -= cost[u]
        else:
            cover.add(v)
            cost[u] -= cost[v]
    return cover