ioftools / networkxMiCe / networkxmaster / networkx / generators / tests / test_classic.py @ 5cef0f13
History  View  Annotate  Download (16.3 KB)
1 
#!/usr/bin/env python


2 
"""

3 
====================

4 
Generators  Classic

5 
====================

6 

7 
Unit tests for various classic graph generators in generators/classic.py

8 
"""

9 
import itertools 
10  
11 
from nose.tools import * 
12 
import networkx as nx 
13 
from networkx import * 
14 
from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic 
15 
from networkx.testing import assert_edges_equal 
16 
from networkx.testing import assert_nodes_equal 
17  
18 
is_isomorphic = graph_could_be_isomorphic 
19  
20  
21 
class TestGeneratorClassic(): 
22 
def test_balanced_tree(self): 
23 
# balanced_tree(r,h) is a tree with (r**(h+1)1)/(r1) edges

24 
for r, h in [(2, 2), (3, 3), (6, 2)]: 
25 
t = balanced_tree(r, h) 
26 
order = t.order() 
27 
assert_true(order == (r**(h + 1)  1) / (r  1)) 
28 
assert_true(is_connected(t)) 
29 
assert_true(t.size() == order  1)

30 
dh = degree_histogram(t) 
31 
assert_equal(dh[0], 0) # no nodes of 0 
32 
assert_equal(dh[1], r**h) # nodes of degree 1 are leaves 
33 
assert_equal(dh[r], 1) # root is degree r 
34 
assert_equal(dh[r + 1], order  r**h  1) # everyone else is degree r+1 
35 
assert_equal(len(dh), r + 2) 
36  
37 
def test_balanced_tree_star(self): 
38 
# balanced_tree(r,1) is the rstar

39 
t = balanced_tree(r=2, h=1) 
40 
assert_true(is_isomorphic(t, star_graph(2)))

41 
t = balanced_tree(r=5, h=1) 
42 
assert_true(is_isomorphic(t, star_graph(5)))

43 
t = balanced_tree(r=10, h=1) 
44 
assert_true(is_isomorphic(t, star_graph(10)))

45  
46 
def test_balanced_tree_path(self): 
47 
"""Tests that the balanced tree with branching factor one is the

48 
path graph.

49 

50 
"""

51 
# A tree of height four has five levels.

52 
T = balanced_tree(1, 4) 
53 
P = path_graph(5)

54 
assert_true(is_isomorphic(T, P)) 
55  
56 
def test_full_rary_tree(self): 
57 
r = 2

58 
n = 9

59 
t = full_rary_tree(r, n) 
60 
assert_equal(t.order(), n) 
61 
assert_true(is_connected(t)) 
62 
dh = degree_histogram(t) 
63 
assert_equal(dh[0], 0) # no nodes of 0 
64 
assert_equal(dh[1], 5) # nodes of degree 1 are leaves 
65 
assert_equal(dh[r], 1) # root is degree r 
66 
assert_equal(dh[r + 1], 9  5  1) # everyone else is degree r+1 
67 
assert_equal(len(dh), r + 2) 
68  
69 
def test_full_rary_tree_balanced(self): 
70 
t = full_rary_tree(2, 15) 
71 
th = balanced_tree(2, 3) 
72 
assert_true(is_isomorphic(t, th)) 
73  
74 
def test_full_rary_tree_path(self): 
75 
t = full_rary_tree(1, 10) 
76 
assert_true(is_isomorphic(t, path_graph(10)))

77  
78 
def test_full_rary_tree_empty(self): 
79 
t = full_rary_tree(0, 10) 
80 
assert_true(is_isomorphic(t, empty_graph(10)))

81 
t = full_rary_tree(3, 0) 
82 
assert_true(is_isomorphic(t, empty_graph(0)))

83  
84 
def test_full_rary_tree_3_20(self): 
85 
t = full_rary_tree(3, 20) 
86 
assert_equal(t.order(), 20)

87  
88 
def test_barbell_graph(self): 
89 
# number of nodes = 2*m1 + m2 (2 m1complete graphs + m2path + 2 edges)

90 
# number of edges = 2*(number_of_edges(m1complete graph) + m2 + 1

91 
m1 = 3

92 
m2 = 5

93 
b = barbell_graph(m1, m2) 
94 
assert_true(number_of_nodes(b) == 2 * m1 + m2)

95 
assert_true(number_of_edges(b) == m1 * (m1  1) + m2 + 1) 
96  
97 
m1 = 4

98 
m2 = 10

99 
b = barbell_graph(m1, m2) 
100 
assert_true(number_of_nodes(b) == 2 * m1 + m2)

101 
assert_true(number_of_edges(b) == m1 * (m1  1) + m2 + 1) 
102  
103 
m1 = 3

104 
m2 = 20

105 
b = barbell_graph(m1, m2) 
106 
assert_true(number_of_nodes(b) == 2 * m1 + m2)

107 
assert_true(number_of_edges(b) == m1 * (m1  1) + m2 + 1) 
108  
109 
# Raise NetworkXError if m1<2

110 
m1 = 1

111 
m2 = 20

112 
assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2) 
113  
114 
# Raise NetworkXError if m2<0

115 
m1 = 5

116 
m2 = 2

117 
assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2) 
118  
119 
# barbell_graph(2,m) = path_graph(m+4)

120 
m1 = 2

121 
m2 = 5

122 
b = barbell_graph(m1, m2) 
123 
assert_true(is_isomorphic(b, path_graph(m2 + 4)))

124  
125 
m1 = 2

126 
m2 = 10

127 
b = barbell_graph(m1, m2) 
128 
assert_true(is_isomorphic(b, path_graph(m2 + 4)))

129  
130 
m1 = 2

131 
m2 = 20

132 
b = barbell_graph(m1, m2) 
133 
assert_true(is_isomorphic(b, path_graph(m2 + 4)))

134  
135 
assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2, 
136 
create_using=DiGraph()) 
137  
138 
mb = barbell_graph(m1, m2, create_using=MultiGraph()) 
139 
assert_edges_equal(mb.edges(), b.edges()) 
140  
141 
def test_binomial_tree(self): 
142 
for n in range(0,4): 
143 
b = binomial_tree(n) 
144 
assert_true(number_of_nodes(b) == 2**n)

145 
assert_true(number_of_edges(b) == (2**n  1)) 
146  
147 
def test_complete_graph(self): 
148 
# complete_graph(m) is a connected graph with

149 
# m nodes and m*(m+1)/2 edges

150 
for m in [0, 1, 3, 5]: 
151 
g = complete_graph(m) 
152 
assert_true(number_of_nodes(g) == m) 
153 
assert_true(number_of_edges(g) == m * (m  1) // 2) 
154  
155 
mg = complete_graph(m, create_using=MultiGraph()) 
156 
assert_edges_equal(mg.edges(), g.edges()) 
157  
158 
g = complete_graph("abc")

159 
assert_nodes_equal(g.nodes(), ['a', 'b', 'c']) 
160 
assert_equal(g.size(), 3)

161  
162 
def test_complete_digraph(self): 
163 
# complete_graph(m) is a connected graph with

164 
# m nodes and m*(m+1)/2 edges

165 
for m in [0, 1, 3, 5]: 
166 
g = complete_graph(m, create_using=DiGraph()) 
167 
assert_true(number_of_nodes(g) == m) 
168 
assert_true(number_of_edges(g) == m * (m  1))

169  
170 
g = complete_graph("abc", create_using=DiGraph())

171 
assert_equal(len(g), 3) 
172 
assert_equal(g.size(), 6)

173 
assert_true(g.is_directed()) 
174  
175 
def test_circular_ladder_graph(self): 
176 
G = circular_ladder_graph(5)

177 
assert_raises(networkx.exception.NetworkXError, circular_ladder_graph, 
178 
5, create_using=DiGraph())

179 
mG = circular_ladder_graph(5, create_using=MultiGraph())

180 
assert_edges_equal(mG.edges(), G.edges()) 
181  
182 
def test_circulant_graph(self): 
183 
# Ci_n(1) is the cycle graph for all n

184 
Ci6_1 = circulant_graph(6, [1]) 
185 
C6 = cycle_graph(6)

186 
assert_edges_equal(Ci6_1.edges(), C6.edges()) 
187  
188 
# Ci_n(1, 2, ..., n div 2) is the complete graph for all n

189 
Ci7 = circulant_graph(7, [1, 2, 3]) 
190 
K7 = complete_graph(7)

191 
assert_edges_equal(Ci7.edges(), K7.edges()) 
192  
193 
# Ci_6(1, 3) is K_3,3 i.e. the utility graph

194 
Ci6_1_3 = circulant_graph(6, [1, 3]) 
195 
K3_3 = complete_bipartite_graph(3, 3) 
196 
assert_true(is_isomorphic(Ci6_1_3, K3_3)) 
197  
198 
def test_cycle_graph(self): 
199 
G = cycle_graph(4)

200 
assert_edges_equal(G.edges(), [(0, 1), (0, 3), (1, 2), (2, 3)]) 
201 
mG = cycle_graph(4, create_using=MultiGraph())

202 
assert_edges_equal(mG.edges(), [(0, 1), (0, 3), (1, 2), (2, 3)]) 
203 
G = cycle_graph(4, create_using=DiGraph())

204 
assert_false(G.has_edge(2, 1)) 
205 
assert_true(G.has_edge(1, 2)) 
206 
assert_true(G.is_directed()) 
207  
208 
G = cycle_graph("abc")

209 
assert_equal(len(G), 3) 
210 
assert_equal(G.size(), 3)

211 
g = cycle_graph("abc", DiGraph())

212 
assert_equal(len(g), 3) 
213 
assert_equal(g.size(), 3)

214 
assert_true(g.is_directed()) 
215  
216 
def test_dorogovtsev_goltsev_mendes_graph(self): 
217 
G = dorogovtsev_goltsev_mendes_graph(0)

218 
assert_edges_equal(G.edges(), [(0, 1)]) 
219 
assert_nodes_equal(list(G), [0, 1]) 
220 
G = dorogovtsev_goltsev_mendes_graph(1)

221 
assert_edges_equal(G.edges(), [(0, 1), (0, 2), (1, 2)]) 
222 
assert_equal(average_clustering(G), 1.0)

223 
assert_equal(sorted(triangles(G).values()), [1, 1, 1]) 
224 
G = dorogovtsev_goltsev_mendes_graph(10)

225 
assert_equal(number_of_nodes(G), 29526)

226 
assert_equal(number_of_edges(G), 59049)

227 
assert_equal(G.degree(0), 1024) 
228 
assert_equal(G.degree(1), 1024) 
229 
assert_equal(G.degree(2), 1024) 
230  
231 
assert_raises(networkx.exception.NetworkXError, 
232 
dorogovtsev_goltsev_mendes_graph, 7,

233 
create_using=DiGraph()) 
234 
assert_raises(networkx.exception.NetworkXError, 
235 
dorogovtsev_goltsev_mendes_graph, 7,

236 
create_using=MultiGraph()) 
237  
238 
def test_create_using(self): 
239 
G = empty_graph() 
240 
assert_true(isinstance(G, Graph))

241 
assert_raises(TypeError, empty_graph, create_using=0.0) 
242 
assert_raises(TypeError, empty_graph, create_using="Graph") 
243  
244 
G = empty_graph(create_using=MultiGraph) 
245 
assert_true(isinstance(G, MultiGraph))

246 
G = empty_graph(create_using=DiGraph) 
247 
assert_true(isinstance(G, DiGraph))

248  
249 
G = empty_graph(create_using=DiGraph, default=MultiGraph) 
250 
assert_true(isinstance(G, DiGraph))

251 
G = empty_graph(create_using=None, default=MultiGraph)

252 
assert_true(isinstance(G, MultiGraph))

253 
G = empty_graph(default=MultiGraph) 
254 
assert_true(isinstance(G, MultiGraph))

255  
256 
G = path_graph(5)

257 
H = empty_graph(create_using=G) 
258 
assert_false(H.is_multigraph()) 
259 
assert_false(H.is_directed()) 
260 
assert_equal(len(H), 0) 
261 
assert_is(G, H) 
262  
263 
H = empty_graph(create_using=MultiGraph()) 
264 
assert_true(H.is_multigraph()) 
265 
assert_false(H.is_directed()) 
266 
assert_is_not(G, H) 
267  
268 
def test_empty_graph(self): 
269 
G = empty_graph() 
270 
assert_equal(number_of_nodes(G), 0)

271 
G = empty_graph(42)

272 
assert_equal(number_of_nodes(G), 42)

273 
assert_equal(number_of_edges(G), 0)

274  
275 
G = empty_graph("abc")

276 
assert_equal(len(G), 3) 
277 
assert_equal(G.size(), 0)

278  
279 
# create empty digraph

280 
G = empty_graph(42, create_using=DiGraph(name="duh")) 
281 
assert_equal(number_of_nodes(G), 42)

282 
assert_equal(number_of_edges(G), 0)

283 
assert_true(isinstance(G, DiGraph))

284  
285 
# create empty multigraph

286 
G = empty_graph(42, create_using=MultiGraph(name="duh")) 
287 
assert_equal(number_of_nodes(G), 42)

288 
assert_equal(number_of_edges(G), 0)

289 
assert_true(isinstance(G, MultiGraph))

290  
291 
# create empty graph from another

292 
pete = petersen_graph() 
293 
G = empty_graph(42, create_using=pete)

294 
assert_equal(number_of_nodes(G), 42)

295 
assert_equal(number_of_edges(G), 0)

296 
assert_true(isinstance(G, Graph))

297  
298 
def test_ladder_graph(self): 
299 
for i, G in [(0, empty_graph(0)), (1, path_graph(2)), 
300 
(2, hypercube_graph(2)), (10, grid_graph([2, 10]))]: 
301 
assert_true(is_isomorphic(ladder_graph(i), G)) 
302  
303 
assert_raises(networkx.exception.NetworkXError, 
304 
ladder_graph, 2, create_using=DiGraph())

305  
306 
g = ladder_graph(2)

307 
mg = ladder_graph(2, create_using=MultiGraph())

308 
assert_edges_equal(mg.edges(), g.edges()) 
309  
310 
def test_lollipop_graph(self): 
311 
# number of nodes = m1 + m2

312 
# number of edges = number_of_edges(complete_graph(m1)) + m2

313 
for m1, m2 in [(3, 5), (4, 10), (3, 20)]: 
314 
b = lollipop_graph(m1, m2) 
315 
assert_equal(number_of_nodes(b), m1 + m2) 
316 
assert_equal(number_of_edges(b), m1 * (m1  1) / 2 + m2) 
317  
318 
# Raise NetworkXError if m<2

319 
assert_raises(networkx.exception.NetworkXError, 
320 
lollipop_graph, 1, 20) 
321  
322 
# Raise NetworkXError if n<0

323 
assert_raises(networkx.exception.NetworkXError, 
324 
lollipop_graph, 5, 2) 
325  
326 
# lollipop_graph(2,m) = path_graph(m+2)

327 
for m1, m2 in [(2, 5), (2, 10), (2, 20)]: 
328 
b = lollipop_graph(m1, m2) 
329 
assert_true(is_isomorphic(b, path_graph(m2 + 2)))

330  
331 
assert_raises(networkx.exception.NetworkXError, 
332 
lollipop_graph, m1, m2, create_using=DiGraph()) 
333  
334 
mb = lollipop_graph(m1, m2, create_using=MultiGraph()) 
335 
assert_edges_equal(mb.edges(), b.edges()) 
336  
337 
g = lollipop_graph([1, 2, 3, 4], "abc") 
338 
assert_equal(len(g), 7) 
339 
assert_equal(g.size(), 9)

340  
341 
def test_null_graph(self): 
342 
assert_equal(number_of_nodes(null_graph()), 0)

343  
344 
def test_path_graph(self): 
345 
p = path_graph(0)

346 
assert_true(is_isomorphic(p, null_graph())) 
347  
348 
p = path_graph(1)

349 
assert_true(is_isomorphic(p, empty_graph(1)))

350  
351 
p = path_graph(10)

352 
assert_true(is_connected(p)) 
353 
assert_equal(sorted(d for n, d in p.degree()), 
354 
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2]) 
355 
assert_equal(p.order()  1, p.size())

356  
357 
dp = path_graph(3, create_using=DiGraph())

358 
assert_true(dp.has_edge(0, 1)) 
359 
assert_false(dp.has_edge(1, 0)) 
360  
361 
mp = path_graph(10, create_using=MultiGraph())

362 
assert_edges_equal(mp.edges(), p.edges()) 
363  
364 
G = path_graph("abc")

365 
assert_equal(len(G), 3) 
366 
assert_equal(G.size(), 2)

367 
g = path_graph("abc", DiGraph())

368 
assert_equal(len(g), 3) 
369 
assert_equal(g.size(), 2)

370 
assert_true(g.is_directed()) 
371  
372 
def test_star_graph(self): 
373 
assert_true(is_isomorphic(star_graph(0), empty_graph(1))) 
374 
assert_true(is_isomorphic(star_graph(1), path_graph(2))) 
375 
assert_true(is_isomorphic(star_graph(2), path_graph(3))) 
376 
assert_true(is_isomorphic(star_graph(5), complete_bipartite_graph(1, 5))) 
377  
378 
s = star_graph(10)

379 
assert_equal(sorted(d for n, d in s.degree()), 
380 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10]) 
381  
382 
assert_raises(networkx.exception.NetworkXError, 
383 
star_graph, 10, create_using=DiGraph())

384  
385 
ms = star_graph(10, create_using=MultiGraph())

386 
assert_edges_equal(ms.edges(), s.edges()) 
387  
388 
G = star_graph("abcdefg")

389 
assert_equal(len(G), 7) 
390 
assert_equal(G.size(), 6)

391  
392 
def test_trivial_graph(self): 
393 
assert_equal(number_of_nodes(trivial_graph()), 1)

394  
395 
def test_turan_graph(self): 
396 
assert_equal(number_of_edges(turan_graph(13, 4)), 63) 
397 
assert_true(is_isomorphic(turan_graph(13, 4), complete_multipartite_graph(3, 4, 3, 3))) 
398  
399 
def test_wheel_graph(self): 
400 
for n, G in [(0, null_graph()), (1, empty_graph(1)), 
401 
(2, path_graph(2)), (3, complete_graph(3)), 
402 
(4, complete_graph(4))]: 
403 
g = wheel_graph(n) 
404 
assert_true(is_isomorphic(g, G)) 
405  
406 
g = wheel_graph(10)

407 
assert_equal(sorted(d for n, d in g.degree()), 
408 
[3, 3, 3, 3, 3, 3, 3, 3, 3, 9]) 
409  
410 
assert_raises(networkx.exception.NetworkXError, 
411 
wheel_graph, 10, create_using=DiGraph())

412  
413 
mg = wheel_graph(10, create_using=MultiGraph())

414 
assert_edges_equal(mg.edges(), g.edges()) 
415  
416 
G = wheel_graph("abc")

417 
assert_equal(len(G), 3) 
418 
assert_equal(G.size(), 3)

419  
420 
def test_complete_0_partite_graph(self): 
421 
"""Tests that the complete 0partite graph is the null graph."""

422 
G = complete_multipartite_graph() 
423 
H = null_graph() 
424 
assert_nodes_equal(G, H) 
425 
assert_edges_equal(G.edges(), H.edges()) 
426  
427 
def test_complete_1_partite_graph(self): 
428 
"""Tests that the complete 1partite graph is the empty graph."""

429 
G = complete_multipartite_graph(3)

430 
H = empty_graph(3)

431 
assert_nodes_equal(G, H) 
432 
assert_edges_equal(G.edges(), H.edges()) 
433  
434 
def test_complete_2_partite_graph(self): 
435 
"""Tests that the complete 2partite graph is the complete bipartite

436 
graph.

437 

438 
"""

439 
G = complete_multipartite_graph(2, 3) 
440 
H = complete_bipartite_graph(2, 3) 
441 
assert_nodes_equal(G, H) 
442 
assert_edges_equal(G.edges(), H.edges()) 
443  
444 
def test_complete_multipartite_graph(self): 
445 
"""Tests for generating the complete multipartite graph."""

446 
G = complete_multipartite_graph(2, 3, 4) 
447 
blocks = [(0, 1), (2, 3, 4), (5, 6, 7, 8)] 
448 
# Within each block, no two vertices should be adjacent.

449 
for block in blocks: 
450 
for u, v in itertools.combinations_with_replacement(block, 2): 
451 
assert_true(v not in G[u]) 
452 
assert_equal(G.nodes[u], G.nodes[v]) 
453 
# Across blocks, all vertices should be adjacent.

454 
for (block1, block2) in itertools.combinations(blocks, 2): 
455 
for u, v in itertools.product(block1, block2): 
456 
assert_true(v in G[u])

457 
assert_not_equal(G.nodes[u], G.nodes[v]) 