Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / drawing / tests / test_layout.py @ 5cef0f13

History | View | Annotate | Download (12 KB)

1
"""Unit tests for layout functions."""
2
from nose import SkipTest
3
from nose.tools import assert_almost_equal, assert_equal, \
4
    assert_false, assert_raises
5
import networkx as nx
6

    
7

    
8
class TestLayout(object):
9
    numpy = 1  # nosetests attribute, use nosetests -a 'not numpy' to skip test
10
    scipy = None
11

    
12
    @classmethod
13
    def setupClass(cls):
14
        global numpy, scipy
15
        try:
16
            import numpy
17
        except ImportError:
18
            raise SkipTest('NumPy not available.')
19
        try:
20
            import scipy
21
        except ImportError:
22
            pass    # Almost all tests still viable
23

    
24
    def setUp(self):
25
        self.Gi = nx.grid_2d_graph(5, 5)
26
        self.Gs = nx.Graph()
27
        nx.add_path(self.Gs, 'abcdef')
28
        self.bigG = nx.grid_2d_graph(25, 25)  # bigger than 500 nodes for sparse
29

    
30
    def test_spring_fixed_without_pos(self):
31
        G = nx.path_graph(4)
32
        assert_raises(ValueError, nx.spring_layout, G, fixed=[0])
33
        pos = {0: (1, 1), 2: (0, 0)}
34
        assert_raises(ValueError, nx.spring_layout, G, fixed=[0, 1], pos=pos)
35
        nx.spring_layout(G, fixed=[0, 2], pos=pos)  # No ValueError
36

    
37
    def test_spring_init_pos(self):
38
        # Tests GH #2448
39
        import math
40
        G = nx.Graph()
41
        G.add_edges_from([(0, 1), (1, 2), (2, 0), (2, 3)])
42

    
43
        init_pos = {0: (0.0, 0.0)}
44
        fixed_pos = [0]
45
        pos = nx.fruchterman_reingold_layout(G, pos=init_pos, fixed=fixed_pos)
46
        has_nan = any(math.isnan(c) for coords in pos.values() for c in coords)
47
        assert_false(has_nan, 'values should not be nan')
48

    
49
    def test_smoke_empty_graph(self):
50
        G = []
51
        vpos = nx.random_layout(G)
52
        vpos = nx.circular_layout(G)
53
        vpos = nx.planar_layout(G)
54
        vpos = nx.spring_layout(G)
55
        vpos = nx.fruchterman_reingold_layout(G)
56
        vpos = nx.spectral_layout(G)
57
        vpos = nx.shell_layout(G)
58
        vpos = nx.bipartite_layout(G, G)
59
        if self.scipy is not None:
60
            vpos = nx.kamada_kawai_layout(G)
61

    
62
    def test_smoke_int(self):
63
        G = self.Gi
64
        vpos = nx.random_layout(G)
65
        vpos = nx.circular_layout(G)
66
        vpos = nx.planar_layout(G)
67
        vpos = nx.spring_layout(G)
68
        vpos = nx.fruchterman_reingold_layout(G)
69
        vpos = nx.fruchterman_reingold_layout(self.bigG)
70
        vpos = nx.spectral_layout(G)
71
        vpos = nx.spectral_layout(G.to_directed())
72
        vpos = nx.spectral_layout(self.bigG)
73
        vpos = nx.spectral_layout(self.bigG.to_directed())
74
        vpos = nx.shell_layout(G)
75
        if self.scipy is not None:
76
            vpos = nx.kamada_kawai_layout(G)
77
            vpos = nx.kamada_kawai_layout(G, dim=1)
78

    
79
    def test_smoke_string(self):
80
        G = self.Gs
81
        vpos = nx.random_layout(G)
82
        vpos = nx.circular_layout(G)
83
        vpos = nx.planar_layout(G)
84
        vpos = nx.spring_layout(G)
85
        vpos = nx.fruchterman_reingold_layout(G)
86
        vpos = nx.spectral_layout(G)
87
        vpos = nx.shell_layout(G)
88
        if self.scipy is not None:
89
            vpos = nx.kamada_kawai_layout(G)
90
            vpos = nx.kamada_kawai_layout(G, dim=1)
91

    
92
    def check_scale_and_center(self, pos, scale, center):
93
        center = numpy.array(center)
94
        low = center - scale
95
        hi = center + scale
96
        vpos = numpy.array(list(pos.values()))
97
        length = vpos.max(0) - vpos.min(0)
98
        assert (length <= 2 * scale).all()
99
        assert (vpos >= low).all()
100
        assert (vpos <= hi).all()
101

    
102
    def test_scale_and_center_arg(self):
103
        sc = self.check_scale_and_center
104
        c = (4, 5)
105
        G = nx.complete_graph(9)
106
        G.add_node(9)
107
        sc(nx.random_layout(G, center=c), scale=0.5, center=(4.5, 5.5))
108
        # rest can have 2*scale length: [-scale, scale]
109
        sc(nx.spring_layout(G, scale=2, center=c), scale=2, center=c)
110
        sc(nx.spectral_layout(G, scale=2, center=c), scale=2, center=c)
111
        sc(nx.circular_layout(G, scale=2, center=c), scale=2, center=c)
112
        sc(nx.shell_layout(G, scale=2, center=c), scale=2, center=c)
113
        if self.scipy is not None:
114
            sc(nx.kamada_kawai_layout(G, scale=2, center=c), scale=2, center=c)
115

    
116
    def test_planar_layout_non_planar_input(self):
117
        G = nx.complete_graph(9)
118
        assert_raises(nx.NetworkXException, nx.planar_layout, G)
119

    
120
    def test_smoke_planar_layout_embedding_input(self):
121
        embedding = nx.PlanarEmbedding()
122
        embedding.set_data({0: [1, 2], 1: [0, 2], 2: [0, 1]})
123
        nx.planar_layout(embedding)
124

    
125
    def test_default_scale_and_center(self):
126
        sc = self.check_scale_and_center
127
        c = (0, 0)
128
        G = nx.complete_graph(9)
129
        G.add_node(9)
130
        sc(nx.random_layout(G), scale=0.5, center=(0.5, 0.5))
131
        sc(nx.spring_layout(G), scale=1, center=c)
132
        sc(nx.spectral_layout(G), scale=1, center=c)
133
        sc(nx.circular_layout(G), scale=1, center=c)
134
        sc(nx.shell_layout(G), scale=1, center=c)
135
        if self.scipy is not None:
136
            sc(nx.kamada_kawai_layout(G), scale=1, center=c)
137

    
138
    def test_circular_planar_and_shell_dim_error(self):
139
        G = nx.path_graph(4)
140
        assert_raises(ValueError, nx.circular_layout, G, dim=1)
141
        assert_raises(ValueError, nx.shell_layout, G, dim=1)
142
        assert_raises(ValueError, nx.shell_layout, G, dim=3)
143
        assert_raises(ValueError, nx.planar_layout, G, dim=1)
144
        assert_raises(ValueError, nx.planar_layout, G, dim=3)
145

    
146
    def test_adjacency_interface_numpy(self):
147
        A = nx.to_numpy_array(self.Gs)
148
        pos = nx.drawing.layout._fruchterman_reingold(A)
149
        assert_equal(pos.shape, (6, 2))
150
        pos = nx.drawing.layout._fruchterman_reingold(A, dim=3)
151
        assert_equal(pos.shape, (6, 3))
152

    
153
    def test_adjacency_interface_scipy(self):
154
        try:
155
            import scipy
156
        except ImportError:
157
            raise SkipTest('scipy not available.')
158
        A = nx.to_scipy_sparse_matrix(self.Gs, dtype='d')
159
        pos = nx.drawing.layout._sparse_fruchterman_reingold(A)
160
        assert_equal(pos.shape, (6, 2))
161
        pos = nx.drawing.layout._sparse_spectral(A)
162
        assert_equal(pos.shape, (6, 2))
163
        pos = nx.drawing.layout._sparse_fruchterman_reingold(A, dim=3)
164
        assert_equal(pos.shape, (6, 3))
165

    
166
    def test_single_nodes(self):
167
        G = nx.path_graph(1)
168
        vpos = nx.shell_layout(G)
169
        assert_false(vpos[0].any())
170
        G = nx.path_graph(3)
171
        vpos = nx.shell_layout(G, [[0], [1, 2]])
172
        assert_false(vpos[0].any())
173

    
174
    def test_smoke_initial_pos_fruchterman_reingold(self):
175
        pos = nx.circular_layout(self.Gi)
176
        npos = nx.fruchterman_reingold_layout(self.Gi, pos=pos)
177

    
178
    def test_fixed_node_fruchterman_reingold(self):
179
        # Dense version (numpy based)
180
        pos = nx.circular_layout(self.Gi)
181
        npos = nx.fruchterman_reingold_layout(self.Gi, pos=pos, fixed=[(0, 0)])
182
        assert_equal(tuple(pos[(0, 0)]), tuple(npos[(0, 0)]))
183
        # Sparse version (scipy based)
184
        pos = nx.circular_layout(self.bigG)
185
        npos = nx.fruchterman_reingold_layout(self.bigG, pos=pos, fixed=[(0, 0)])
186
        for axis in range(2):
187
            assert_almost_equal(pos[(0, 0)][axis], npos[(0, 0)][axis])
188

    
189
    def test_center_parameter(self):
190
        G = nx.path_graph(1)
191
        vpos = nx.random_layout(G, center=(1, 1))
192
        vpos = nx.circular_layout(G, center=(1, 1))
193
        assert_equal(tuple(vpos[0]), (1, 1))
194
        vpos = nx.planar_layout(G, center=(1, 1))
195
        assert_equal(tuple(vpos[0]), (1, 1))
196
        vpos = nx.spring_layout(G, center=(1, 1))
197
        assert_equal(tuple(vpos[0]), (1, 1))
198
        vpos = nx.fruchterman_reingold_layout(G, center=(1, 1))
199
        assert_equal(tuple(vpos[0]), (1, 1))
200
        vpos = nx.spectral_layout(G, center=(1, 1))
201
        assert_equal(tuple(vpos[0]), (1, 1))
202
        vpos = nx.shell_layout(G, center=(1, 1))
203
        assert_equal(tuple(vpos[0]), (1, 1))
204

    
205
    def test_center_wrong_dimensions(self):
206
        G = nx.path_graph(1)
207
        assert_raises(ValueError, nx.random_layout, G, center=(1, 1, 1))
208
        assert_raises(ValueError, nx.circular_layout, G, center=(1, 1, 1))
209
        assert_raises(ValueError, nx.planar_layout, G, center=(1, 1, 1))
210
        assert_raises(ValueError, nx.spring_layout, G, center=(1, 1, 1))
211
        assert_raises(ValueError, nx.fruchterman_reingold_layout, G, center=(1, 1, 1))
212
        assert_raises(ValueError, nx.fruchterman_reingold_layout, G, dim=3, center=(1, 1))
213
        assert_raises(ValueError, nx.spectral_layout, G, center=(1, 1, 1))
214
        assert_raises(ValueError, nx.spectral_layout, G, dim=3, center=(1, 1))
215
        assert_raises(ValueError, nx.shell_layout, G, center=(1, 1, 1))
216

    
217
    def test_empty_graph(self):
218
        G = nx.empty_graph()
219
        vpos = nx.random_layout(G, center=(1, 1))
220
        assert_equal(vpos, {})
221
        vpos = nx.circular_layout(G, center=(1, 1))
222
        assert_equal(vpos, {})
223
        vpos = nx.planar_layout(G, center=(1, 1))
224
        assert_equal(vpos, {})
225
        vpos = nx.bipartite_layout(G, G)
226
        assert_equal(vpos, {})
227
        vpos = nx.spring_layout(G, center=(1, 1))
228
        assert_equal(vpos, {})
229
        vpos = nx.fruchterman_reingold_layout(G, center=(1, 1))
230
        assert_equal(vpos, {})
231
        vpos = nx.spectral_layout(G, center=(1, 1))
232
        assert_equal(vpos, {})
233
        vpos = nx.shell_layout(G, center=(1, 1))
234
        assert_equal(vpos, {})
235

    
236
    def test_bipartite_layout(self):
237
        G = nx.complete_bipartite_graph(3,5)
238
        top, bottom = nx.bipartite.sets(G)
239

    
240
        vpos = nx.bipartite_layout(G, top)
241
        assert_equal(len(vpos), len(G))
242

    
243
        top_x = vpos[list(top)[0]][0]
244
        bottom_x = vpos[list(bottom)[0]][0]
245
        for node in top:
246
            assert_equal(vpos[node][0], top_x)
247
        for node in bottom:
248
            assert_equal(vpos[node][0], bottom_x)
249

    
250
        vpos = nx.bipartite_layout(G, top,
251
                                   align='horizontal',
252
                                   center=(2,2),
253
                                   scale=2,
254
                                   aspect_ratio=1)
255
        assert_equal(len(vpos), len(G))
256

    
257
        top_y = vpos[list(top)[0]][1]
258
        bottom_y = vpos[list(bottom)[0]][1]
259
        for node in top:
260
            assert_equal(vpos[node][1], top_y)
261
        for node in bottom:
262
            assert_equal(vpos[node][1], bottom_y)
263

    
264
        assert_raises(ValueError, nx.bipartite_layout, G, top, align='foo')
265

    
266
    def test_kamada_kawai_costfn_1d(self):
267
        costfn = nx.drawing.layout._kamada_kawai_costfn
268

    
269
        pos = numpy.array([4.0, 7.0])
270
        invdist = 1 / numpy.array([[0.1, 2.0], [2.0, 0.3]])
271

    
272
        cost, grad = costfn(pos, numpy, invdist, meanweight=0, dim=1)
273

    
274
        assert_almost_equal(cost, ((3 / 2.0 - 1) ** 2))
275
        assert_almost_equal(grad[0], -0.5)
276
        assert_almost_equal(grad[1], 0.5)
277

    
278
    def test_kamada_kawai_costfn_2d(self):
279
        costfn = nx.drawing.layout._kamada_kawai_costfn
280

    
281
        pos = numpy.array([[1.3, -3.2],
282
                           [2.7, -0.3],
283
                           [5.1, 2.5]])
284
        invdist = 1 / numpy.array([[0.1, 2.1, 1.7],
285
                                   [2.1, 0.2, 0.6],
286
                                   [1.7, 0.6, 0.3]])
287
        meanwt = 0.3
288

    
289
        cost, grad = costfn(pos.ravel(), numpy, invdist,
290
                            meanweight=meanwt, dim=2)
291

    
292
        expected_cost = 0.5 * meanwt * numpy.sum(numpy.sum(pos, axis=0) ** 2)
293
        for i in range(pos.shape[0]):
294
            for j in range(i + 1, pos.shape[0]):
295
                expected_cost += (numpy.linalg.norm(pos[i] - pos[j]) * invdist[i][j] - 1.0) ** 2
296

    
297
        assert_almost_equal(cost, expected_cost)
298

    
299
        dx = 1e-4
300
        for nd in range(pos.shape[0]):
301
            for dm in range(pos.shape[1]):
302
                idx = nd * pos.shape[1] + dm
303
                pos0 = pos.flatten()
304

    
305
                pos0[idx] += dx
306
                cplus = costfn(pos0, numpy, invdist,
307
                               meanweight=meanwt, dim=pos.shape[1])[0]
308

    
309
                pos0[idx] -= 2 * dx
310
                cminus = costfn(pos0, numpy, invdist,
311
                                meanweight=meanwt, dim=pos.shape[1])[0]
312

    
313
                assert_almost_equal(grad[idx], (cplus - cminus) / (2 * dx),
314
                                    places=5)