This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
Source code for networkx.algorithms.approximation.vertex_cover
# -*- 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 <email@example.com> # All rights reserved. # BSD license. from networkx.utils import * __all__ = ["min_weighted_vertex_cover"] __author__ = """Nicholas Mancuso (firstname.lastname@example.org)""" @not_implemented_for('directed')[docs]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 ---------- ..  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)