ioftools / networkxMiCe / networkxmaster / networkx / algorithms / approximation / dominating_set.py @ 5cef0f13
History  View  Annotate  Download (4.29 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20112012 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 costeffectiveness of greedily choosing the given

80 
node.

81 

82 
`node_and_neighborhood` is a twotuple 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 costeffective 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 nonempty NetworkX graph!") 
132 
return maximal_matching(G)
