Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.4 KB)

1
# -*- 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)