Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.29 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
"""Functions for finding node and edge dominating sets.
7

8
A `dominating set`_ for an undirected graph *G* with vertex set *V*
9
and edge set *E* is a subset *D* of *V* such that every vertex not in
10
*D* is adjacent to at least one member of *D*. An `edge dominating set`_
11
is a subset *F* of *E* such that every edge not in *F* is
12
incident to an endpoint of at least one edge in *F*.
13

14
.. _dominating set: https://en.wikipedia.org/wiki/Dominating_set
15
.. _edge dominating set: https://en.wikipedia.org/wiki/Edge_dominating_set
16

17
"""
18
from __future__ import division
19

    
20
from ..matching import maximal_matching
21
from ...utils import not_implemented_for
22

    
23
__all__ = ["min_weighted_dominating_set",
24
           "min_edge_dominating_set"]
25

    
26
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)"""
27

    
28

    
29
# TODO Why doesn't this algorithm work for directed graphs?
30
@not_implemented_for('directed')
31
def min_weighted_dominating_set(G, weight=None):
32
    r"""Returns a dominating set that approximates the minimum weight node
33
    dominating set.
34

35
    Parameters
36
    ----------
37
    G : NetworkX graph
38
        Undirected graph.
39

40
    weight : string
41
        The node attribute storing the weight of an node. If provided,
42
        the node attribute with this key must be a number for each
43
        node. If not provided, each node is assumed to have weight one.
44

45
    Returns
46
    -------
47
    min_weight_dominating_set : set
48
        A set of nodes, the sum of whose weights is no more than `(\log
49
        w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of
50
        each node in the graph and `w(V^*)` denotes the sum of the
51
        weights of each node in the minimum weight dominating set.
52

53
    Notes
54
    -----
55
    This algorithm computes an approximate minimum weighted dominating
56
    set for the graph `G`. The returned solution has weight `(\log
57
    w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each
58
    node in the graph and `w(V^*)` denotes the sum of the weights of
59
    each node in the minimum weight dominating set for the graph.
60

61
    This implementation of the algorithm runs in $O(m)$ time, where $m$
62
    is the number of edges in the graph.
63

64
    References
65
    ----------
66
    .. [1] Vazirani, Vijay V.
67
           *Approximation Algorithms*.
68
           Springer Science & Business Media, 2001.
69

70
    """
71
    # The unique dominating set for the null graph is the empty set.
72
    if len(G) == 0:
73
        return set()
74

    
75
    # This is the dominating set that will eventually be returned.
76
    dom_set = set()
77

    
78
    def _cost(node_and_neighborhood):
79
        """Returns the cost-effectiveness of greedily choosing the given
80
        node.
81

82
        `node_and_neighborhood` is a two-tuple comprising a node and its
83
        closed neighborhood.
84

85
        """
86
        v, neighborhood = node_and_neighborhood
87
        return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)
88

    
89
    # This is a set of all vertices not already covered by the
90
    # dominating set.
91
    vertices = set(G)
92
    # This is a dictionary mapping each node to the closed neighborhood
93
    # of that node.
94
    neighborhoods = {v: {v} | set(G[v]) for v in G}
95

    
96
    # Continue until all vertices are adjacent to some node in the
97
    # dominating set.
98
    while vertices:
99
        # Find the most cost-effective node to add, along with its
100
        # closed neighborhood.
101
        dom_node, min_set = min(neighborhoods.items(), key=_cost)
102
        # Add the node to the dominating set and reduce the remaining
103
        # set of nodes to cover.
104
        dom_set.add(dom_node)
105
        del neighborhoods[dom_node]
106
        vertices -= min_set
107

    
108
    return dom_set
109

    
110

    
111
def min_edge_dominating_set(G):
112
    r"""Returns minimum cardinality edge dominating set.
113

114
    Parameters
115
    ----------
116
    G : NetworkX graph
117
      Undirected graph
118

119
    Returns
120
    -------
121
    min_edge_dominating_set : set
122
      Returns a set of dominating edges whose size is no more than 2 * OPT.
123

124
    Notes
125
    -----
126
    The algorithm computes an approximate solution to the edge dominating set
127
    problem. The result is no more than 2 * OPT in terms of size of the set.
128
    Runtime of the algorithm is $O(|E|)$.
129
    """
130
    if not G:
131
        raise ValueError("Expected non-empty NetworkX graph!")
132
    return maximal_matching(G)