## iof-tools / networkxMiCe / networkx-master / networkx / generators / tests / test_random_graphs.py @ 5cef0f13

History | View | Annotate | Download (10.4 KB)

1 | 5cef0f13 | tiamilani | ```
# -*- encoding: utf-8 -*-
``` |
---|---|---|---|

2 | ```
# test_random_graphs.py - unit tests for random graph generators
``` |
||

3 | ```
#
``` |
||

4 | ```
# Copyright 2010-2019 NetworkX developers.
``` |
||

5 | ```
#
``` |
||

6 | ```
# This file is part of NetworkX.
``` |
||

7 | ```
#
``` |
||

8 | ```
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
``` |
||

9 | ```
# information.
``` |
||

10 | ```
"""Unit tests for the :mod:`networkx.generators.random_graphs` module.
``` |
||

11 | ```
``` |
||

12 | ```
"""
``` |
||

13 | from nose.tools import assert_almost_equal |
||

14 | from nose.tools import assert_greater |
||

15 | from nose.tools import assert_less |
||

16 | from nose.tools import assert_equal |
||

17 | from nose.tools import assert_raises |
||

18 | from nose.tools import assert_true |
||

19 | |||

20 | from networkx.exception import NetworkXError |
||

21 | from networkx.generators.random_graphs import barabasi_albert_graph |
||

22 | from networkx.generators.random_graphs import dual_barabasi_albert_graph |
||

23 | from networkx.generators.random_graphs import extended_barabasi_albert_graph |
||

24 | from networkx.generators.random_graphs import binomial_graph |
||

25 | from networkx.generators.random_graphs import connected_watts_strogatz_graph |
||

26 | from networkx.generators.random_graphs import dense_gnm_random_graph |
||

27 | from networkx.generators.random_graphs import erdos_renyi_graph |
||

28 | from networkx.generators.random_graphs import fast_gnp_random_graph |
||

29 | from networkx.generators.random_graphs import gnm_random_graph |
||

30 | from networkx.generators.random_graphs import gnp_random_graph |
||

31 | from networkx.generators.random_graphs import newman_watts_strogatz_graph |
||

32 | from networkx.generators.random_graphs import powerlaw_cluster_graph |
||

33 | from networkx.generators.random_graphs import random_kernel_graph |
||

34 | from networkx.generators.random_graphs import random_lobster |
||

35 | from networkx.generators.random_graphs import random_powerlaw_tree |
||

36 | from networkx.generators.random_graphs import random_powerlaw_tree_sequence |
||

37 | from networkx.generators.random_graphs import random_regular_graph |
||

38 | from networkx.generators.random_graphs import random_shell_graph |
||

39 | from networkx.generators.random_graphs import watts_strogatz_graph |
||

40 | |||

41 | |||

42 | class TestGeneratorsRandom(object): |
||

43 | |||

44 | def smoke_test_random_graph(self): |
||

45 | ```
seed = 42
``` |
||

46 | G = gnp_random_graph(100, 0.25, seed) |
||

47 | G = gnp_random_graph(100, 0.25, seed, directed=True) |
||

48 | G = binomial_graph(100, 0.25, seed) |
||

49 | G = erdos_renyi_graph(100, 0.25, seed) |
||

50 | G = fast_gnp_random_graph(100, 0.25, seed) |
||

51 | G = fast_gnp_random_graph(100, 0.25, seed, directed=True) |
||

52 | G = gnm_random_graph(100, 20, seed) |
||

53 | G = gnm_random_graph(100, 20, seed, directed=True) |
||

54 | G = dense_gnm_random_graph(100, 20, seed) |
||

55 | |||

56 | G = watts_strogatz_graph(10, 2, 0.25, seed) |
||

57 | assert_equal(len(G), 10) |
||

58 | ```
assert_equal(G.number_of_edges(), 10)
``` |
||

59 | |||

60 | G = connected_watts_strogatz_graph(10, 2, 0.1, tries=10, seed=seed) |
||

61 | assert_equal(len(G), 10) |
||

62 | ```
assert_equal(G.number_of_edges(), 10)
``` |
||

63 | assert_raises(NetworkXError, connected_watts_strogatz_graph, \ |
||

64 | 10, 2, 0.1, tries=0) |
||

65 | |||

66 | G = watts_strogatz_graph(10, 4, 0.25, seed) |
||

67 | assert_equal(len(G), 10) |
||

68 | ```
assert_equal(G.number_of_edges(), 20)
``` |
||

69 | |||

70 | G = newman_watts_strogatz_graph(10, 2, 0.0, seed) |
||

71 | assert_equal(len(G), 10) |
||

72 | ```
assert_equal(G.number_of_edges(), 10)
``` |
||

73 | |||

74 | G = newman_watts_strogatz_graph(10, 4, 0.25, seed) |
||

75 | assert_equal(len(G), 10) |
||

76 | ```
assert_true(G.number_of_edges() >= 20)
``` |
||

77 | |||

78 | G = barabasi_albert_graph(100, 1, seed) |
||

79 | G = barabasi_albert_graph(100, 3, seed) |
||

80 | assert_equal(G.number_of_edges(), (97 * 3)) |
||

81 | |||

82 | G = extended_barabasi_albert_graph(100, 1, 0, 0, seed) |
||

83 | ```
assert_equal(G.number_of_edges(), 99)
``` |
||

84 | G = extended_barabasi_albert_graph(100, 3, 0, 0, seed) |
||

85 | assert_equal(G.number_of_edges(), 97 * 3) |
||

86 | G = extended_barabasi_albert_graph(100, 1, 0, 0.5, seed) |
||

87 | ```
assert_equal(G.number_of_edges(), 99)
``` |
||

88 | G = extended_barabasi_albert_graph(100, 2, 0.5, 0, seed) |
||

89 | assert_greater(G.number_of_edges(), 100 * 3) |
||

90 | assert_less(G.number_of_edges(), 100 * 4) |
||

91 | |||

92 | G = extended_barabasi_albert_graph(100, 2, 0.3, 0.3, seed) |
||

93 | assert_greater(G.number_of_edges(), 100 * 2) |
||

94 | assert_less(G.number_of_edges(), 100 * 4) |
||

95 | |||

96 | G = powerlaw_cluster_graph(100, 1, 1.0, seed) |
||

97 | G = powerlaw_cluster_graph(100, 3, 0.0, seed) |
||

98 | assert_equal(G.number_of_edges(), (97 * 3)) |
||

99 | |||

100 | G = random_regular_graph(10, 20, seed) |
||

101 | |||

102 | assert_raises(NetworkXError, random_regular_graph, 3, 21) |
||

103 | assert_raises(NetworkXError, random_regular_graph, 33, 21) |
||

104 | |||

105 | constructor = [(10, 20, 0.8), (20, 40, 0.8)] |
||

106 | G = random_shell_graph(constructor, seed) |
||

107 | |||

108 | G = random_lobster(10, 0.1, 0.5, seed) |
||

109 | |||

110 | ```
# difficult to find seed that requires few tries
``` |
||

111 | seq = random_powerlaw_tree_sequence(10, 3, seed=14, tries=1) |
||

112 | G = random_powerlaw_tree(10, 3, seed=14, tries=1) |
||

113 | |||

114 | def test_dual_barabasi_albert(self, m1=1, m2=4, p=0.5): |
||

115 | ```
"""
``` |
||

116 | ```
Tests that the dual BA random graph generated behaves consistently.
``` |
||

117 | ```
``` |
||

118 | ```
Tests the exceptions are raised as expected.
``` |
||

119 | ```
``` |
||

120 | ```
The graphs generation are repeated several times to prevent lucky shots
``` |
||

121 | ```
``` |
||

122 | ```
"""
``` |
||

123 | ```
seed = 42
``` |
||

124 | ```
repeats = 2
``` |
||

125 | |||

126 | ```
while repeats:
``` |
||

127 | ```
repeats -= 1
``` |
||

128 | |||

129 | ```
# This should be BA with m = m1
``` |
||

130 | ```
BA1 = barabasi_albert_graph(100, m1, seed)
``` |
||

131 | DBA1 = dual_barabasi_albert_graph(100, m1, m2, 1, seed) |
||

132 | assert_equal(BA1.size(), DBA1.size()) |
||

133 | |||

134 | ```
# This should be BA with m = m2
``` |
||

135 | ```
BA2 = barabasi_albert_graph(100, m2, seed)
``` |
||

136 | DBA2 = dual_barabasi_albert_graph(100, m1, m2, 0, seed) |
||

137 | assert_equal(BA2.size(), DBA2.size()) |
||

138 | |||

139 | ```
# Testing exceptions
``` |
||

140 | dbag = dual_barabasi_albert_graph |
||

141 | ```
assert_raises(NetworkXError, dbag, m1, m1, m2, 0)
``` |
||

142 | ```
assert_raises(NetworkXError, dbag, m2, m1, m2, 0)
``` |
||

143 | assert_raises(NetworkXError, dbag, 100, m1, m2, -0.5) |
||

144 | assert_raises(NetworkXError, dbag, 100, m1, m2, 1.5) |
||

145 | |||

146 | def test_extended_barabasi_albert(self, m=2): |
||

147 | ```
"""
``` |
||

148 | ```
Tests that the extended BA random graph generated behaves consistently.
``` |
||

149 | ```
``` |
||

150 | ```
Tests the exceptions are raised as expected.
``` |
||

151 | ```
``` |
||

152 | ```
The graphs generation are repeated several times to prevent lucky-shots
``` |
||

153 | ```
``` |
||

154 | ```
"""
``` |
||

155 | ```
seed = 42
``` |
||

156 | ```
repeats = 2
``` |
||

157 | ```
BA_model = barabasi_albert_graph(100, m, seed)
``` |
||

158 | BA_model_edges = BA_model.number_of_edges() |
||

159 | |||

160 | ```
while repeats:
``` |
||

161 | ```
repeats -= 1
``` |
||

162 | |||

163 | ```
# This behaves just like BA, the number of edges must be the same
``` |
||

164 | G1 = extended_barabasi_albert_graph(100, m, 0, 0, seed) |
||

165 | assert_equal(G1.size(), BA_model_edges) |
||

166 | |||

167 | ```
# More than twice more edges should have been added
``` |
||

168 | G1 = extended_barabasi_albert_graph(100, m, 0.8, 0, seed) |
||

169 | ```
assert_greater(G1.size(), BA_model_edges * 2)
``` |
||

170 | |||

171 | ```
# Only edge rewiring, so the number of edges less than original
``` |
||

172 | G2 = extended_barabasi_albert_graph(100, m, 0, 0.8, seed) |
||

173 | assert_equal(G2.size(), BA_model_edges) |
||

174 | |||

175 | ```
# Mixed scenario: less edges than G1 and more edges than G2
``` |
||

176 | G3 = extended_barabasi_albert_graph(100, m, 0.3, 0.3, seed) |
||

177 | assert_greater(G3.size(), G2.size()) |
||

178 | assert_less(G3.size(), G1.size()) |
||

179 | |||

180 | ```
# Testing exceptions
``` |
||

181 | ebag = extended_barabasi_albert_graph |
||

182 | assert_raises(NetworkXError, ebag, m, m, 0, 0) |
||

183 | assert_raises(NetworkXError, ebag, 1, 0.5, 0, 0) |
||

184 | assert_raises(NetworkXError, ebag, 100, 2, 0.5, 0.5) |
||

185 | |||

186 | def test_random_zero_regular_graph(self): |
||

187 | ```
"""Tests that a 0-regular graph has the correct number of nodes and
``` |
||

188 | ```
edges.
``` |
||

189 | ```
``` |
||

190 | ```
"""
``` |
||

191 | ```
seed = 42
``` |
||

192 | G = random_regular_graph(0, 10, seed) |
||

193 | assert_equal(len(G), 10) |
||

194 | assert_equal(sum(1 for _ in G.edges()), 0) |
||

195 | |||

196 | def test_gnp(self): |
||

197 | for generator in [gnp_random_graph, binomial_graph, erdos_renyi_graph, |
||

198 | fast_gnp_random_graph]: |
||

199 | G = generator(10, -1.1) |
||

200 | assert_equal(len(G), 10) |
||

201 | assert_equal(sum(1 for _ in G.edges()), 0) |
||

202 | |||

203 | G = generator(10, 0.1) |
||

204 | assert_equal(len(G), 10) |
||

205 | |||

206 | G = generator(10, 0.1, seed=42) |
||

207 | assert_equal(len(G), 10) |
||

208 | |||

209 | G = generator(10, 1.1) |
||

210 | assert_equal(len(G), 10) |
||

211 | assert_equal(sum(1 for _ in G.edges()), 45) |
||

212 | |||

213 | G = generator(10, -1.1, directed=True) |
||

214 | assert_true(G.is_directed()) |
||

215 | assert_equal(len(G), 10) |
||

216 | assert_equal(sum(1 for _ in G.edges()), 0) |
||

217 | |||

218 | G = generator(10, 0.1, directed=True) |
||

219 | assert_true(G.is_directed()) |
||

220 | assert_equal(len(G), 10) |
||

221 | |||

222 | G = generator(10, 1.1, directed=True) |
||

223 | assert_true(G.is_directed()) |
||

224 | assert_equal(len(G), 10) |
||

225 | assert_equal(sum(1 for _ in G.edges()), 90) |
||

226 | |||

227 | ```
# assert that random graphs generate all edges for p close to 1
``` |
||

228 | ```
edges = 0
``` |
||

229 | ```
runs = 100
``` |
||

230 | for i in range(runs): |
||

231 | edges += sum(1 for _ in generator(10, 0.99999, directed=True).edges()) |
||

232 | assert_almost_equal(edges / float(runs), 90, delta=runs * 2.0 / 100) |
||

233 | |||

234 | def test_gnm(self): |
||

235 | G = gnm_random_graph(10, 3) |
||

236 | assert_equal(len(G), 10) |
||

237 | assert_equal(sum(1 for _ in G.edges()), 3) |
||

238 | |||

239 | G = gnm_random_graph(10, 3, seed=42) |
||

240 | assert_equal(len(G), 10) |
||

241 | assert_equal(sum(1 for _ in G.edges()), 3) |
||

242 | |||

243 | G = gnm_random_graph(10, 100) |
||

244 | assert_equal(len(G), 10) |
||

245 | assert_equal(sum(1 for _ in G.edges()), 45) |
||

246 | |||

247 | G = gnm_random_graph(10, 100, directed=True) |
||

248 | assert_equal(len(G), 10) |
||

249 | assert_equal(sum(1 for _ in G.edges()), 90) |
||

250 | |||

251 | G = gnm_random_graph(10, -1.1) |
||

252 | assert_equal(len(G), 10) |
||

253 | assert_equal(sum(1 for _ in G.edges()), 0) |
||

254 | |||

255 | def test_watts_strogatz_big_k(self): |
||

256 | assert_raises(NetworkXError, watts_strogatz_graph, 10, 10, 0.25) |
||

257 | assert_raises(NetworkXError, newman_watts_strogatz_graph, 10, 10, 0.25) |
||

258 | ```
# could create an infinite loop, now doesn't
``` |
||

259 | ```
# infinite loop used to occur when a node has degree n-1 and needs to rewire
``` |
||

260 | watts_strogatz_graph(10, 9, 0.25, seed=0) |
||

261 | newman_watts_strogatz_graph(10, 9, 0.5, seed=0) |
||

262 | |||

263 | def test_random_kernel_graph(self): |
||

264 | def integral(u, w, z): |
||

265 | ```
return c * (z - w)
``` |
||

266 | |||

267 | def root(u, w, r): |
||

268 | ```
return r / c + w
``` |
||

269 | ```
c = 1
``` |
||

270 | ```
graph = random_kernel_graph(1000, integral, root)
``` |
||

271 | graph = random_kernel_graph(1000, integral, root, seed=42) |
||

272 | assert_equal(len(graph), 1000) |