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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
# -*- coding: utf-8 -*-
# Copyright (C) 2011-2012 by
# Nicholas Mancuso <nick.mancuso@gmail.com>
# All rights reserved.
# BSD license.
"""Functions for finding node and edge dominating sets.
A `dominating set`_ for an undirected graph *G* with vertex set *V*
and edge set *E* is a subset *D* of *V* such that every vertex not in
*D* is adjacent to at least one member of *D*. An `edge dominating set`_
is a subset *F* of *E* such that every edge not in *F* is
incident to an endpoint of at least one edge in *F*.
.. _dominating set: https://en.wikipedia.org/wiki/Dominating_set
.. _edge dominating set: https://en.wikipedia.org/wiki/Edge_dominating_set
"""
from __future__ import division
from ..matching import maximal_matching
from ...utils import not_implemented_for
__all__ = ["min_weighted_dominating_set",
"min_edge_dominating_set"]
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)"""
# TODO Why doesn't this algorithm work for directed graphs?
@not_implemented_for('directed')
def min_weighted_dominating_set(G, weight=None):
"""Returns a dominating set that approximates the minimum weight node
dominating set.
Parameters
----------
G : NetworkX graph
Undirected graph.
weight : string
The node attribute storing the weight of an node. If provided,
the node attribute with this key must be a number for each
node. If not provided, each node is assumed to have weight one.
Returns
-------
min_weight_dominating_set : set
A set of nodes, the sum of whose weights is no more than `(\log
w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of
each node in the graph and `w(V^*)` denotes the sum of the
weights of each node in the minimum weight dominating set.
Notes
-----
This algorithm computes an approximate minimum weighted dominating
set for the graph `G`. The returned solution has weight `(\log
w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each
node in the graph and `w(V^*)` denotes the sum of the weights of
each node in the minimum weight dominating set for the graph.
This implementation of the algorithm runs in $O(m)$ time, where $m$
is the number of edges in the graph.
References
----------
.. [1] Vazirani, Vijay V.
*Approximation Algorithms*.
Springer Science & Business Media, 2001.
"""
# The unique dominating set for the null graph is the empty set.
if len(G) == 0:
return set()
# This is the dominating set that will eventually be returned.
dom_set = set()
def _cost(node_and_neighborhood):
"""Returns the cost-effectiveness of greedily choosing the given
node.
`node_and_neighborhood` is a two-tuple comprising a node and its
closed neighborhood.
"""
v, neighborhood = node_and_neighborhood
return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)
# This is a set of all vertices not already covered by the
# dominating set.
vertices = set(G)
# This is a dictionary mapping each node to the closed neighborhood
# of that node.
neighborhoods = {v: {v} | set(G[v]) for v in G}
# Continue until all vertices are adjacent to some node in the
# dominating set.
while vertices:
# Find the most cost-effective node to add, along with its
# closed neighborhood.
dom_node, min_set = min(neighborhoods.items(), key=_cost)
# Add the node to the dominating set and reduce the remaining
# set of nodes to cover.
dom_set.add(dom_node)
del neighborhoods[dom_node]
vertices -= min_set
return dom_set
def min_edge_dominating_set(G):
r"""Return minimum cardinality edge dominating set.
Parameters
----------
G : NetworkX graph
Undirected graph
Returns
-------
min_edge_dominating_set : set
Returns a set of dominating edges whose size is no more than 2 * OPT.
Notes
-----
The algorithm computes an approximate solution to the edge dominating set
problem. The result is no more than 2 * OPT in terms of size of the set.
Runtime of the algorithm is $O(|E|)$.
"""
if not G:
raise ValueError("Expected non-empty NetworkX graph!")
return maximal_matching(G)
|
