Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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)/(r-1) 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 r-star
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 m1-complete graphs + m2-path + 2 edges)
90
        # number of edges = 2*(number_of_edges(m1-complete 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 0-partite 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 1-partite 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 2-partite 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])