Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / linalg / tests / test_algebraic_connectivity.py @ 5cef0f13

History | View | Annotate | Download (11.4 KB)

1
from math import sqrt
2
import networkx as nx
3
from nose import SkipTest
4
from nose.tools import *
5

    
6
try:
7
    from scikits.sparse.cholmod import cholesky
8
    _cholesky = cholesky
9
except ImportError:
10
    _cholesky = None
11

    
12
if _cholesky is None:
13
    methods = ('tracemin_pcg', 'tracemin_lu', 'lanczos', 'lobpcg')
14
else:
15
    methods = ('tracemin_pcg', 'tracemin_chol', 'tracemin_lu', 'lanczos', 'lobpcg')
16

    
17

    
18
def check_eigenvector(A, l, x):
19
    nx = numpy.linalg.norm(x)
20
    # Check zeroness.
21
    assert_not_almost_equal(nx, 0)
22
    y = A * x
23
    ny = numpy.linalg.norm(y)
24
    # Check collinearity.
25
    assert_almost_equal(numpy.dot(x, y), nx * ny)
26
    # Check eigenvalue.
27
    assert_almost_equal(ny, l * nx)
28

    
29

    
30
class TestAlgebraicConnectivity(object):
31

    
32
    numpy = 1
33

    
34
    @classmethod
35
    def setupClass(cls):
36
        global numpy
37
        try:
38
            import numpy.linalg
39
            import scipy.sparse
40
        except ImportError:
41
            raise SkipTest('SciPy not available.')
42

    
43
    def test_directed(self):
44
        G = nx.DiGraph()
45
        for method in self._methods:
46
            assert_raises(nx.NetworkXNotImplemented, nx.algebraic_connectivity,
47
                          G, method=method)
48
            assert_raises(nx.NetworkXNotImplemented, nx.fiedler_vector, G,
49
                          method=method)
50

    
51
    def test_null_and_singleton(self):
52
        G = nx.Graph()
53
        for method in self._methods:
54
            assert_raises(nx.NetworkXError, nx.algebraic_connectivity, G,
55
                          method=method)
56
            assert_raises(nx.NetworkXError, nx.fiedler_vector, G,
57
                          method=method)
58
        G.add_edge(0, 0)
59
        for method in self._methods:
60
            assert_raises(nx.NetworkXError, nx.algebraic_connectivity, G,
61
                          method=method)
62
            assert_raises(nx.NetworkXError, nx.fiedler_vector, G,
63
                          method=method)
64

    
65
    def test_disconnected(self):
66
        G = nx.Graph()
67
        G.add_nodes_from(range(2))
68
        for method in self._methods:
69
            assert_equal(nx.algebraic_connectivity(G), 0)
70
            assert_raises(nx.NetworkXError, nx.fiedler_vector, G,
71
                          method=method)
72
        G.add_edge(0, 1, weight=0)
73
        for method in self._methods:
74
            assert_equal(nx.algebraic_connectivity(G), 0)
75
            assert_raises(nx.NetworkXError, nx.fiedler_vector, G,
76
                          method=method)
77

    
78
    def test_unrecognized_method(self):
79
        G = nx.path_graph(4)
80
        assert_raises(nx.NetworkXError, nx.algebraic_connectivity, G,
81
                      method='unknown')
82
        assert_raises(nx.NetworkXError, nx.fiedler_vector, G, method='unknown')
83

    
84
    def test_two_nodes(self):
85
        G = nx.Graph()
86
        G.add_edge(0, 1, weight=1)
87
        A = nx.laplacian_matrix(G)
88
        for method in self._methods:
89
            assert_almost_equal(nx.algebraic_connectivity(
90
                G, tol=1e-12, method=method), 2)
91
            x = nx.fiedler_vector(G, tol=1e-12, method=method)
92
            check_eigenvector(A, 2, x)
93
        G = nx.MultiGraph()
94
        G.add_edge(0, 0, spam=1e8)
95
        G.add_edge(0, 1, spam=1)
96
        G.add_edge(0, 1, spam=-2)
97
        A = -3 * nx.laplacian_matrix(G, weight='spam')
98
        for method in self._methods:
99
            assert_almost_equal(nx.algebraic_connectivity(
100
                G, weight='spam', tol=1e-12, method=method), 6)
101
            x = nx.fiedler_vector(G, weight='spam', tol=1e-12, method=method)
102
            check_eigenvector(A, 6, x)
103

    
104
    def test_abbreviation_of_method(self):
105
        G = nx.path_graph(8)
106
        A = nx.laplacian_matrix(G)
107
        sigma = 2 - sqrt(2 + sqrt(2))
108
        ac = nx.algebraic_connectivity(G, tol=1e-12, method='tracemin')
109
        assert_almost_equal(ac, sigma)
110
        x = nx.fiedler_vector(G, tol=1e-12, method='tracemin')
111
        check_eigenvector(A, sigma, x)
112

    
113
    def test_path(self):
114
        G = nx.path_graph(8)
115
        A = nx.laplacian_matrix(G)
116
        sigma = 2 - sqrt(2 + sqrt(2))
117
        for method in self._methods:
118
            ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
119
            assert_almost_equal(ac, sigma)
120
            x = nx.fiedler_vector(G, tol=1e-12, method=method)
121
            check_eigenvector(A, sigma, x)
122

    
123
    def test_problematic_graph_issue_2381(self):
124
        G = nx.path_graph(4)
125
        G.add_edges_from([(4, 2), (5, 1)])
126
        A = nx.laplacian_matrix(G)
127
        sigma = 0.438447187191
128
        for method in self._methods:
129
            ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
130
            assert_almost_equal(ac, sigma)
131
            x = nx.fiedler_vector(G, tol=1e-12, method=method)
132
            check_eigenvector(A, sigma, x)
133

    
134
    def test_cycle(self):
135
        G = nx.cycle_graph(8)
136
        A = nx.laplacian_matrix(G)
137
        sigma = 2 - sqrt(2)
138
        for method in self._methods:
139
            ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
140
            assert_almost_equal(ac, sigma)
141
            x = nx.fiedler_vector(G, tol=1e-12, method=method)
142
            check_eigenvector(A, sigma, x)
143

    
144
    def test_seed_argument(self):
145
        G = nx.cycle_graph(8)
146
        A = nx.laplacian_matrix(G)
147
        sigma = 2 - sqrt(2)
148
        for method in self._methods:
149
            ac = nx.algebraic_connectivity(G, tol=1e-12, method=method, seed=1)
150
            assert_almost_equal(ac, sigma)
151
            x = nx.fiedler_vector(G, tol=1e-12, method=method, seed=1)
152
            check_eigenvector(A, sigma, x)
153

    
154
    def test_buckminsterfullerene(self):
155
        G = nx.Graph(
156
            [(1, 10), (1, 41), (1, 59), (2, 12), (2, 42), (2, 60), (3, 6),
157
             (3, 43), (3, 57), (4, 8), (4, 44), (4, 58), (5, 13), (5, 56),
158
             (5, 57), (6, 10), (6, 31), (7, 14), (7, 56), (7, 58), (8, 12),
159
             (8, 32), (9, 23), (9, 53), (9, 59), (10, 15), (11, 24), (11, 53),
160
             (11, 60), (12, 16), (13, 14), (13, 25), (14, 26), (15, 27),
161
             (15, 49), (16, 28), (16, 50), (17, 18), (17, 19), (17, 54),
162
             (18, 20), (18, 55), (19, 23), (19, 41), (20, 24), (20, 42),
163
             (21, 31), (21, 33), (21, 57), (22, 32), (22, 34), (22, 58),
164
             (23, 24), (25, 35), (25, 43), (26, 36), (26, 44), (27, 51),
165
             (27, 59), (28, 52), (28, 60), (29, 33), (29, 34), (29, 56),
166
             (30, 51), (30, 52), (30, 53), (31, 47), (32, 48), (33, 45),
167
             (34, 46), (35, 36), (35, 37), (36, 38), (37, 39), (37, 49),
168
             (38, 40), (38, 50), (39, 40), (39, 51), (40, 52), (41, 47),
169
             (42, 48), (43, 49), (44, 50), (45, 46), (45, 54), (46, 55),
170
             (47, 54), (48, 55)])
171
        for normalized in (False, True):
172
            if not normalized:
173
                A = nx.laplacian_matrix(G)
174
                sigma = 0.2434017461399311
175
            else:
176
                A = nx.normalized_laplacian_matrix(G)
177
                sigma = 0.08113391537997749
178
            for method in methods:
179
                try:
180
                    assert_almost_equal(nx.algebraic_connectivity(
181
                        G, normalized=normalized, tol=1e-12, method=method),
182
                        sigma)
183
                    x = nx.fiedler_vector(G, normalized=normalized, tol=1e-12,
184
                                          method=method)
185
                    check_eigenvector(A, sigma, x)
186
                except nx.NetworkXError as e:
187
                    if e.args not in (('Cholesky solver unavailable.',),
188
                                      ('LU solver unavailable.',)):
189
                        raise
190

    
191
    _methods = methods
192

    
193

    
194
class TestSpectralOrdering(object):
195

    
196
    numpy = 1
197

    
198
    @classmethod
199
    def setupClass(cls):
200
        global numpy
201
        try:
202
            import numpy.linalg
203
            import scipy.sparse
204
        except ImportError:
205
            raise SkipTest('SciPy not available.')
206

    
207
    def test_nullgraph(self):
208
        for graph in (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph):
209
            G = graph()
210
            assert_raises(nx.NetworkXError, nx.spectral_ordering, G)
211

    
212
    def test_singleton(self):
213
        for graph in (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph):
214
            G = graph()
215
            G.add_node('x')
216
            assert_equal(nx.spectral_ordering(G), ['x'])
217
            G.add_edge('x', 'x', weight=33)
218
            G.add_edge('x', 'x', weight=33)
219
            assert_equal(nx.spectral_ordering(G), ['x'])
220

    
221
    def test_unrecognized_method(self):
222
        G = nx.path_graph(4)
223
        assert_raises(nx.NetworkXError, nx.spectral_ordering, G,
224
                      method='unknown')
225

    
226
    def test_three_nodes(self):
227
        G = nx.Graph()
228
        G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1)],
229
                                  weight='spam')
230
        for method in self._methods:
231
            order = nx.spectral_ordering(G, weight='spam', method=method)
232
            assert_equal(set(order), set(G))
233
            ok_(set([1, 3]) in (set(order[:-1]), set(order[1:])))
234
        G = nx.MultiDiGraph()
235
        G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1), (2, 3, 2)])
236
        for method in self._methods:
237
            order = nx.spectral_ordering(G, method=method)
238
            assert_equal(set(order), set(G))
239
            ok_(set([2, 3]) in (set(order[:-1]), set(order[1:])))
240

    
241
    def test_path(self):
242
        # based on setupClass numpy is installed if we get here
243
        from numpy.random import shuffle
244
        path = list(range(10))
245
        shuffle(path)
246
        G = nx.Graph()
247
        nx.add_path(G, path)
248
        for method in self._methods:
249
            order = nx.spectral_ordering(G, method=method)
250
            ok_(order in [path, list(reversed(path))])
251

    
252
    def test_seed_argument(self):
253
        # based on setupClass numpy is installed if we get here
254
        from numpy.random import shuffle
255
        path = list(range(10))
256
        shuffle(path)
257
        G = nx.Graph()
258
        nx.add_path(G, path)
259
        for method in self._methods:
260
            order = nx.spectral_ordering(G, method=method, seed=1)
261
            ok_(order in [path, list(reversed(path))])
262

    
263
    def test_disconnected(self):
264
        G = nx.Graph()
265
        nx.add_path(G, range(0, 10, 2))
266
        nx.add_path(G, range(1, 10, 2))
267
        for method in self._methods:
268
            order = nx.spectral_ordering(G, method=method)
269
            assert_equal(set(order), set(G))
270
            seqs = [list(range(0, 10, 2)), list(range(8, -1, -2)),
271
                    list(range(1, 10, 2)), list(range(9, -1, -2))]
272
            ok_(order[:5] in seqs)
273
            ok_(order[5:] in seqs)
274

    
275
    def test_cycle(self):
276
        path = list(range(10))
277
        G = nx.Graph()
278
        nx.add_path(G, path, weight=5)
279
        G.add_edge(path[-1], path[0], weight=1)
280
        A = nx.laplacian_matrix(G).todense()
281
        for normalized in (False, True):
282
            for method in methods:
283
                try:
284
                    order = nx.spectral_ordering(G, normalized=normalized,
285
                                                 method=method)
286
                except nx.NetworkXError as e:
287
                    if e.args not in (('Cholesky solver unavailable.',),
288
                                      ('LU solver unavailable.',)):
289
                        raise
290
                else:
291
                    if not normalized:
292
                        ok_(order in [[1, 2, 0, 3, 4, 5, 6, 9, 7, 8],
293
                                      [8, 7, 9, 6, 5, 4, 3, 0, 2, 1]])
294
                    else:
295
                        ok_(order in [[1, 2, 3, 0, 4, 5, 9, 6, 7, 8],
296
                                      [8, 7, 6, 9, 5, 4, 0, 3, 2, 1]])
297

    
298
    _methods = methods