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
|
import pytest
import networkx as nx
def test_dominating_set():
G = nx.gnp_random_graph(100, 0.1)
D = nx.dominating_set(G)
assert nx.is_dominating_set(G, D)
D = nx.dominating_set(G, start_with=0)
assert nx.is_dominating_set(G, D)
def test_complete():
"""In complete graphs each node is a dominating set.
Thus the dominating set has to be of cardinality 1.
"""
K4 = nx.complete_graph(4)
assert len(nx.dominating_set(K4)) == 1
K5 = nx.complete_graph(5)
assert len(nx.dominating_set(K5)) == 1
def test_raise_dominating_set():
with pytest.raises(nx.NetworkXError):
G = nx.path_graph(4)
D = nx.dominating_set(G, start_with=10)
def test_is_dominating_set():
G = nx.path_graph(4)
d = {1, 3}
assert nx.is_dominating_set(G, d)
d = {0, 2}
assert nx.is_dominating_set(G, d)
d = {1}
assert not nx.is_dominating_set(G, d)
def test_wikipedia_is_dominating_set():
"""Example from https://en.wikipedia.org/wiki/Dominating_set"""
G = nx.cycle_graph(4)
G.add_edges_from([(0, 4), (1, 4), (2, 5)])
assert nx.is_dominating_set(G, {4, 3, 5})
assert nx.is_dominating_set(G, {0, 2})
assert nx.is_dominating_set(G, {1, 2})
def test_is_connected_dominating_set():
G = nx.path_graph(4)
D = {1, 2}
assert nx.is_connected_dominating_set(G, D)
D = {1, 3}
assert not nx.is_connected_dominating_set(G, D)
D = {2, 3}
assert nx.is_connected(nx.subgraph(G, D))
assert not nx.is_connected_dominating_set(G, D)
def test_null_graph_connected_dominating_set():
G = nx.Graph()
assert 0 == len(nx.connected_dominating_set(G))
def test_single_node_graph_connected_dominating_set():
G = nx.Graph()
G.add_node(1)
CD = nx.connected_dominating_set(G)
assert nx.is_connected_dominating_set(G, CD)
def test_raise_disconnected_graph_connected_dominating_set():
with pytest.raises(nx.NetworkXError):
G = nx.Graph()
G.add_node(1)
G.add_node(2)
nx.connected_dominating_set(G)
def test_complete_graph_connected_dominating_set():
K5 = nx.complete_graph(5)
assert 1 == len(nx.connected_dominating_set(K5))
K7 = nx.complete_graph(7)
assert 1 == len(nx.connected_dominating_set(K7))
def test_docstring_example_connected_dominating_set():
G = nx.Graph(
[
(1, 2),
(1, 3),
(1, 4),
(1, 5),
(1, 6),
(2, 7),
(3, 8),
(4, 9),
(5, 10),
(6, 11),
(7, 12),
(8, 12),
(9, 12),
(10, 12),
(11, 12),
]
)
assert {1, 2, 3, 4, 5, 6, 7} == nx.connected_dominating_set(G)
@pytest.mark.parametrize("seed", [1, 13, 29])
@pytest.mark.parametrize("n,k,p", [(10, 3, 0.2), (100, 10, 0.7), (1000, 50, 0.5)])
def test_connected_watts_strogatz_graph_connected_dominating_set(n, k, p, seed):
G = nx.connected_watts_strogatz_graph(n, k, p, seed=seed)
D = nx.connected_dominating_set(G)
assert nx.is_connected_dominating_set(G, D)
|
