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
|
# -*- coding: utf-8 -*-
import networkx as nx
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>'])
__all__ = [ 'dominating_set', 'is_dominating_set']
def dominating_set(G, start_with=None):
r"""Finds a dominating set for the graph G.
A dominating set for a graph `G = (V, E)` is a node subset `D` of `V`
such that every node not in `D` is adjacent to at least one member
of `D` [1]_.
Parameters
----------
G : NetworkX graph
start_with : Node (default=None)
Node to use as a starting point for the algorithm.
Returns
-------
D : set
A dominating set for G.
Notes
-----
This function is an implementation of algorithm 7 in [2]_ which
finds some dominating set, not necessarily the smallest one.
See also
--------
is_dominating_set
References
----------
.. [1] http://en.wikipedia.org/wiki/Dominating_set
.. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms.
http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
"""
all_nodes = set(G)
if start_with is None:
v = set(G).pop() # pick a node
else:
if start_with not in G:
raise nx.NetworkXError('node %s not in G' % start_with)
v = start_with
D = set([v])
ND = set(G[v])
other = all_nodes - ND - D
while other:
w = other.pop()
D.add(w)
ND.update([nbr for nbr in G[w] if nbr not in D])
other = all_nodes - ND - D
return D
def is_dominating_set(G, nbunch):
r"""Checks if nodes in nbunch are a dominating set for G.
A dominating set for a graph `G = (V, E)` is a node subset `D` of `V`
such that every node not in `D` is adjacent to at least one member
of `D` [1]_.
Parameters
----------
G : NetworkX graph
nbunch : Node container
See also
--------
dominating_set
References
----------
.. [1] http://en.wikipedia.org/wiki/Dominating_set
"""
testset = set(n for n in nbunch if n in G)
nbrs = set()
for n in testset:
nbrs.update(G[n])
if len(set(G) - testset - nbrs) > 0:
return False
else:
return True
|
