Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.6 KB)

1
from itertools import combinations
2
from math import sqrt
3
import random
4

    
5
from nose.tools import assert_equal
6
from nose.tools import assert_false
7
from nose.tools import assert_true
8

    
9
import networkx as nx
10
from networkx.generators.geometric import euclidean
11

    
12

    
13
def l1dist(x, y):
14
    return sum(abs(a - b) for a, b in zip(x, y))
15

    
16

    
17
class TestRandomGeometricGraph(object):
18
    """Unit tests for the :func:`~networkx.random_geometric_graph`
19
    function.
20

21
    """
22

    
23
    def test_number_of_nodes(self):
24
        G = nx.random_geometric_graph(50, 0.25, seed=42)
25
        assert_equal(len(G), 50)
26
        G = nx.random_geometric_graph(range(50), 0.25, seed=42)
27
        assert_equal(len(G), 50)
28

    
29
    def test_distances(self):
30
        """Tests that pairs of vertices adjacent if and only if they are
31
        within the prescribed radius.
32

33
        """
34
        # Use the Euclidean metric, the default according to the
35
        # documentation.
36
        dist = euclidean
37
        G = nx.random_geometric_graph(50, 0.25)
38
        for u, v in combinations(G, 2):
39
            # Adjacent vertices must be within the given distance.
40
            if v in G[u]:
41
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
42
            # Nonadjacent vertices must be at greater distance.
43
            else:
44
                assert_false(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
45

    
46
    def test_p(self):
47
        """Tests for providing an alternate distance metric to the
48
        generator.
49

50
        """
51
        # Use the L1 metric.
52
        dist = l1dist
53
        G = nx.random_geometric_graph(50, 0.25, p=1)
54
        for u, v in combinations(G, 2):
55
            # Adjacent vertices must be within the given distance.
56
            if v in G[u]:
57
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
58
            # Nonadjacent vertices must be at greater distance.
59
            else:
60
                assert_false(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
61

    
62
    def test_node_names(self):
63
        """Tests using values other than sequential numbers as node IDs.
64

65
        """
66
        import string
67
        nodes = list(string.ascii_lowercase)
68
        G = nx.random_geometric_graph(nodes, 0.25)
69
        assert_equal(len(G), len(nodes))
70

    
71
        dist = euclidean
72
        for u, v in combinations(G, 2):
73
            # Adjacent vertices must be within the given distance.
74
            if v in G[u]:
75
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
76
            # Nonadjacent vertices must be at greater distance.
77
            else:
78
                assert_false(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
79

    
80

    
81
class TestSoftRandomGeometricGraph(object):
82
    """Unit tests for the :func:`~networkx.soft_random_geometric_graph`
83
    function.
84

85
    """
86

    
87
    def test_number_of_nodes(self):
88
        G = nx.soft_random_geometric_graph(50, 0.25, seed=42)
89
        assert_equal(len(G), 50)
90
        G = nx.soft_random_geometric_graph(range(50), 0.25, seed=42)
91
        assert_equal(len(G), 50)
92

    
93
    def test_distances(self):
94
        """Tests that pairs of vertices adjacent if and only if they are
95
        within the prescribed radius.
96

97
        """
98
        # Use the Euclidean metric, the default according to the
99
        # documentation.
100
        def dist(x, y): return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
101
        G = nx.soft_random_geometric_graph(50, 0.25)
102
        for u, v in combinations(G, 2):
103
            # Adjacent vertices must be within the given distance.
104
            if v in G[u]:
105
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
106

    
107
    def test_p(self):
108
        """Tests for providing an alternate distance metric to the
109
        generator.
110

111
        """
112
        # Use the L1 metric.
113
        def dist(x, y): return sum(abs(a - b) for a, b in zip(x, y))
114
        G = nx.soft_random_geometric_graph(50, 0.25, p=1)
115
        for u, v in combinations(G, 2):
116
            # Adjacent vertices must be within the given distance.
117
            if v in G[u]:
118
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
119

    
120
    def test_node_names(self):
121
        """Tests using values other than sequential numbers as node IDs.
122

123
        """
124
        import string
125
        nodes = list(string.ascii_lowercase)
126
        G = nx.soft_random_geometric_graph(nodes, 0.25)
127
        assert_equal(len(G), len(nodes))
128

    
129
        def dist(x, y): return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
130
        for u, v in combinations(G, 2):
131
            # Adjacent vertices must be within the given distance.
132
            if v in G[u]:
133
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
134

    
135
    def test_p_dist_default(self):
136
        """Tests default p_dict = 0.5 returns graph with edge count <= RGG with
137
           same n, radius, dim and positions
138

139
        """
140
        nodes = 50
141
        dim = 2
142
        pos = {v: [random.random() for i in range(dim)] for v in range(nodes)}
143
        RGG = nx.random_geometric_graph(50, 0.25, pos=pos)
144
        SRGG = nx.soft_random_geometric_graph(50, 0.25, pos=pos)
145
        assert_true(len(SRGG.edges()) <= len(RGG.edges()))
146

    
147
    def test_p_dist_zero(self):
148
        """Tests if p_dict = 0 returns disconencted graph with 0 edges
149

150
        """
151
        def p_dist(dist):
152
            return 0
153

    
154
        G = nx.soft_random_geometric_graph(50, 0.25, p_dist=p_dist)
155
        assert_true(len(G.edges) == 0)
156

    
157

    
158
def join(G, u, v, theta, alpha, metric):
159
    """Returns ``True`` if and only if the nodes whose attributes are
160
    ``du`` and ``dv`` should be joined, according to the threshold
161
    condition for geographical threshold graphs.
162

163
    ``G`` is an undirected NetworkX graph, and ``u`` and ``v`` are nodes
164
    in that graph. The nodes must have node attributes ``'pos'`` and
165
    ``'weight'``.
166

167
    ``metric`` is a distance metric.
168

169
    """
170
    du, dv = G.nodes[u], G.nodes[v]
171
    u_pos, v_pos = du['pos'], dv['pos']
172
    u_weight, v_weight = du['weight'], dv['weight']
173
    return (u_weight + v_weight) * metric(u_pos, v_pos) ** alpha >= theta
174

    
175

    
176
class TestGeographicalThresholdGraph(object):
177
    """Unit tests for the :func:`~networkx.geographical_threshold_graph`
178
    function.
179

180
    """
181

    
182
    def test_number_of_nodes(self):
183
        G = nx.geographical_threshold_graph(50, 100, seed=42)
184
        assert_equal(len(G), 50)
185
        G = nx.geographical_threshold_graph(range(50), 100, seed=42)
186
        assert_equal(len(G), 50)
187

    
188
    def test_distances(self):
189
        """Tests that pairs of vertices adjacent if and only if their
190
        distances meet the given threshold.
191

192
        """
193
        # Use the Euclidean metric and alpha = -2
194
        # the default according to the documentation.
195
        dist = euclidean
196
        G = nx.geographical_threshold_graph(50, 10)
197
        for u, v in combinations(G, 2):
198
            # Adjacent vertices must exceed the threshold.
199
            if v in G[u]:
200
                assert_true(join(G, u, v, 10, -2, dist))
201
            # Nonadjacent vertices must not exceed the threshold.
202
            else:
203
                assert_false(join(G, u, v, 10, -2, dist))
204

    
205
    def test_metric(self):
206
        """Tests for providing an alternate distance metric to the
207
        generator.
208

209
        """
210
        # Use the L1 metric.
211
        dist = l1dist
212
        G = nx.geographical_threshold_graph(50, 10, metric=dist)
213
        for u, v in combinations(G, 2):
214
            # Adjacent vertices must exceed the threshold.
215
            if v in G[u]:
216
                assert_true(join(G, u, v, 10, -2, dist))
217
            # Nonadjacent vertices must not exceed the threshold.
218
            else:
219
                assert_false(join(G, u, v, 10, -2, dist))
220

    
221
    def test_p_dist_zero(self):
222
        """Tests if p_dict = 0 returns disconencted graph with 0 edges
223

224
        """
225
        def p_dist(dist):
226
            return 0
227

    
228
        G = nx.geographical_threshold_graph(50, 1, p_dist=p_dist)
229
        assert_true(len(G.edges) == 0)
230

    
231

    
232
class TestWaxmanGraph(object):
233
    """Unit tests for the :func:`~networkx.waxman_graph` function."""
234

    
235
    def test_number_of_nodes_1(self):
236
        G = nx.waxman_graph(50, 0.5, 0.1, seed=42)
237
        assert_equal(len(G), 50)
238
        G = nx.waxman_graph(range(50), 0.5, 0.1, seed=42)
239
        assert_equal(len(G), 50)
240

    
241
    def test_number_of_nodes_2(self):
242
        G = nx.waxman_graph(50, 0.5, 0.1, L=1)
243
        assert_equal(len(G), 50)
244
        G = nx.waxman_graph(range(50), 0.5, 0.1, L=1)
245
        assert_equal(len(G), 50)
246

    
247
    def test_metric(self):
248
        """Tests for providing an alternate distance metric to the
249
        generator.
250

251
        """
252
        # Use the L1 metric.
253
        dist = l1dist
254
        G = nx.waxman_graph(50, 0.5, 0.1, metric=dist)
255
        assert_equal(len(G), 50)
256

    
257

    
258
class TestNavigableSmallWorldGraph(object):
259

    
260
    def test_navigable_small_world(self):
261
        G = nx.navigable_small_world_graph(5, p=1, q=0, seed=42)
262
        gg = nx.grid_2d_graph(5, 5).to_directed()
263
        assert_true(nx.is_isomorphic(G, gg))
264

    
265
        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=3)
266
        gg = nx.grid_graph([5, 5, 5]).to_directed()
267
        assert_true(nx.is_isomorphic(G, gg))
268

    
269
        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=1)
270
        gg = nx.grid_graph([5]).to_directed()
271
        assert_true(nx.is_isomorphic(G, gg))
272

    
273

    
274
class TestThresholdedRandomGeometricGraph(object):
275
    """Unit tests for the :func:`~networkx.thresholded_random_geometric_graph`
276
    function.
277

278
    """
279

    
280
    def test_number_of_nodes(self):
281
        G = nx.thresholded_random_geometric_graph(50, 0.2, 0.1, seed=42)
282
        assert_equal(len(G), 50)
283
        G = nx.thresholded_random_geometric_graph(range(50), 0.2, 0.1)
284
        assert_equal(len(G), 50)
285

    
286
    def test_distances(self):
287
        """Tests that pairs of vertices adjacent if and only if they are
288
        within the prescribed radius.
289

290
        """
291
        # Use the Euclidean metric, the default according to the
292
        # documentation.
293
        def dist(x, y): return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
294
        G = nx.thresholded_random_geometric_graph(50, 0.25, 0.1)
295
        for u, v in combinations(G, 2):
296
            # Adjacent vertices must be within the given distance.
297
            if v in G[u]:
298
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
299

    
300
    def test_p(self):
301
        """Tests for providing an alternate distance metric to the
302
        generator.
303

304
        """
305
        # Use the L1 metric.
306
        def dist(x, y): return sum(abs(a - b) for a, b in zip(x, y))
307
        G = nx.thresholded_random_geometric_graph(50, 0.25, 0.1,  p=1)
308
        for u, v in combinations(G, 2):
309
            # Adjacent vertices must be within the given distance.
310
            if v in G[u]:
311
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
312

    
313
    def test_node_names(self):
314
        """Tests using values other than sequential numbers as node IDs.
315

316
        """
317
        import string
318
        nodes = list(string.ascii_lowercase)
319
        G = nx.thresholded_random_geometric_graph(nodes, 0.25, 0.1)
320
        assert_equal(len(G), len(nodes))
321

    
322
        def dist(x, y): return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
323
        for u, v in combinations(G, 2):
324
            # Adjacent vertices must be within the given distance.
325
            if v in G[u]:
326
                assert_true(dist(G.nodes[u]['pos'], G.nodes[v]['pos']) <= 0.25)
327

    
328
    def test_theta(self):
329
        """Tests that pairs of vertices adjacent if and only if their sum
330
        weights exceeds the threshold parameter theta.
331
        """
332
        G = nx.thresholded_random_geometric_graph(50, 0.25, 0.1)
333

    
334
        for u, v in combinations(G, 2):
335
            # Adjacent vertices must be within the given distance.
336
            if v in G[u]:
337
                assert_true((G.nodes[u]['weight'] + G.nodes[v]['weight']) >= 0.1)