/usr/lib/python2.7/dist-packages/networkx/algorithms/approximation/vertex_cover.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | # -*- coding: utf-8 -*-
"""
************
Vertex Cover
************
Given an undirected graph `G = (V, E)` and a function w assigning nonnegative
weights to its vertices, find a minimum weight subset of V such that each edge
in E is incident to at least one vertex in the subset.
http://en.wikipedia.org/wiki/Vertex_cover
"""
# Copyright (C) 2011-2012 by
# Nicholas Mancuso <nick.mancuso@gmail.com>
# All rights reserved.
# BSD license.
from networkx.utils import *
__all__ = ["min_weighted_vertex_cover"]
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)"""
@not_implemented_for('directed')
def min_weighted_vertex_cover(G, weight=None):
r"""2-OPT Local Ratio for Minimum Weighted Vertex Cover
Find an approximate minimum weighted vertex cover of a graph.
Parameters
----------
G : NetworkX graph
Undirected graph
weight : None or string, optional (default = None)
If None, every edge has weight/distance/cost 1. If a string, use this
edge attribute as the edge weight. Any edge attribute not present
defaults to 1.
Returns
-------
min_weighted_cover : set
Returns a set of vertices whose weight sum is no more than 2 * OPT.
Notes
-----
Local-Ratio algorithm for computing an approximate vertex cover.
Algorithm greedily reduces the costs over edges and iteratively
builds a cover. Worst-case runtime is `O(|E|)`.
References
----------
.. [1] Bar-Yehuda, R., & 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
"""
weight_func = lambda nd: nd.get(weight, 1)
cost = dict((n, weight_func(nd)) for n, nd in G.nodes(data=True))
# while there are edges uncovered, continue
for u,v in G.edges_iter():
# select some uncovered edge
min_cost = min([cost[u], cost[v]])
cost[u] -= min_cost
cost[v] -= min_cost
return set(u for u in cost if cost[u] == 0)
|