Statistics
| Branch: | Revision:

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

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2011-2012 by ``` ```# Nicholas Mancuso ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Author: ``` ```# Nicholas Mancuso ``` ```"""Functions for computing an approximate minimum weight vertex cover. ``` ``` ``` ```A |vertex cover|_ is a subset of nodes such that each edge in the graph ``` ```is incident to at least one node in the subset. ``` ``` ``` ```.. _vertex cover: https://en.wikipedia.org/wiki/Vertex_cover ``` ```.. |vertex cover| replace:: *vertex cover* ``` ``` ``` ```""" ``` ```__all__ = ["min_weighted_vertex_cover"] ``` ```def min_weighted_vertex_cover(G, weight=None): ``` ``` r"""Returns an approximate minimum weighted vertex cover. ``` ``` ``` ``` The set of nodes returned by this function is guaranteed to be a ``` ``` vertex cover, and the total weight of the set is guaranteed to be at ``` ``` most twice the total weight of the minimum weight vertex cover. In ``` ``` other words, ``` ``` ``` ``` .. math:: ``` ``` ``` ``` w(S) \leq 2 * w(S^*), ``` ``` ``` ``` where \$S\$ is the vertex cover returned by this function, ``` ``` \$S^*\$ is the vertex cover of minimum weight out of all vertex ``` ``` covers of the graph, and \$w\$ is the function that computes the ``` ``` sum of the weights of each node in that given set. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` weight : string, optional (default = None) ``` ``` If None, every node has weight 1. If a string, use this node ``` ``` attribute as the node weight. A node without this attribute is ``` ``` assumed to have weight 1. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` min_weighted_cover : set ``` ``` Returns a set of nodes whose weight sum is no more than twice ``` ``` the weight sum of the minimum weight vertex cover. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` For a directed graph, a vertex cover has the same definition: a set ``` ``` of nodes such that each edge in the graph is incident to at least ``` ``` one node in the set. Whether the node is the head or tail of the ``` ``` directed edge is ignored. ``` ``` ``` ``` This is the local-ratio algorithm for computing an approximate ``` ``` vertex cover. The algorithm greedily reduces the costs over edges, ``` ``` iteratively building a cover. The worst-case runtime of this ``` ``` implementation is \$O(m \log n)\$, where \$n\$ is the number ``` ``` of nodes and \$m\$ the number of edges in the graph. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  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 ``` ``` ``` ``` ``` ``` """ ``` ``` cost = dict(G.nodes(data=weight, default=1)) ``` ``` # While there are uncovered edges, choose an uncovered and update ``` ``` # the cost of the remaining edges. ``` ``` for u, v in G.edges(): ``` ``` min_cost = min(cost[u], cost[v]) ``` ``` cost[u] -= min_cost ``` ``` cost[v] -= min_cost ``` ``` return {u for u, c in cost.items() if c == 0} ```