Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tests / test_distance_measures.py @ 5cef0f13

History | View | Annotate | Download (9.18 KB)

1
#!/usr/bin/env python
2
from random import Random
3
from nose import SkipTest
4
from nose.tools import assert_equal, assert_is_instance, \
5
        assert_raises, raises, assert_less_equal, assert_false, \
6
        assert_true
7

    
8
import networkx as nx
9
from networkx import convert_node_labels_to_integers as cnlti
10

    
11

    
12
class TestDistance:
13
    def setUp(self):
14
        G = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
15
        self.G = G
16

    
17
    def test_eccentricity(self):
18
        assert_equal(nx.eccentricity(self.G, 1), 6)
19
        e = nx.eccentricity(self.G)
20
        assert_equal(e[1], 6)
21

    
22
        sp = dict(nx.shortest_path_length(self.G))
23
        e = nx.eccentricity(self.G, sp=sp)
24
        assert_equal(e[1], 6)
25

    
26
        e = nx.eccentricity(self.G, v=1)
27
        assert_equal(e, 6)
28

    
29
        # This behavior changed in version 1.8 (ticket #739)
30
        e = nx.eccentricity(self.G, v=[1, 1])
31
        assert_equal(e[1], 6)
32
        e = nx.eccentricity(self.G, v=[1, 2])
33
        assert_equal(e[1], 6)
34

    
35
        # test against graph with one node
36
        G = nx.path_graph(1)
37
        e = nx.eccentricity(G)
38
        assert_equal(e[0], 0)
39
        e = nx.eccentricity(G, v=0)
40
        assert_equal(e, 0)
41
        assert_raises(nx.NetworkXError, nx.eccentricity, G, 1)
42

    
43
        # test against empty graph
44
        G = nx.empty_graph()
45
        e = nx.eccentricity(G)
46
        assert_equal(e, {})
47

    
48
    def test_diameter(self):
49
        assert_equal(nx.diameter(self.G), 6)
50

    
51
    def test_radius(self):
52
        assert_equal(nx.radius(self.G), 4)
53

    
54
    def test_periphery(self):
55
        assert_equal(set(nx.periphery(self.G)), set([1, 4, 13, 16]))
56

    
57
    def test_center(self):
58
        assert_equal(set(nx.center(self.G)), set([6, 7, 10, 11]))
59

    
60
    def test_bound_diameter(self):
61
        assert_equal(nx.diameter(self.G, usebounds=True), 6)
62

    
63
    def test_bound_radius(self):
64
        assert_equal(nx.radius(self.G, usebounds=True), 4)
65

    
66
    def test_bound_periphery(self):
67
        result = set([1, 4, 13, 16])
68
        assert_equal(set(nx.periphery(self.G, usebounds=True)), result)
69

    
70
    def test_bound_center(self):
71
        result = set([6, 7, 10, 11])
72
        assert_equal(set(nx.center(self.G, usebounds=True)), result)
73

    
74
    def test_radius_exception(self):
75
        G = nx.Graph()
76
        G.add_edge(1, 2)
77
        G.add_edge(3, 4)
78
        assert_raises(nx.NetworkXError, nx.diameter, G)
79

    
80
    @raises(nx.NetworkXError)
81
    def test_eccentricity_infinite(self):
82
        G = nx.Graph([(1, 2), (3, 4)])
83
        e = nx.eccentricity(G)
84

    
85
    @raises(nx.NetworkXError)
86
    def test_eccentricity_undirected_not_connected(self):
87
        G = nx.Graph([(1, 2), (3, 4)])
88
        e = nx.eccentricity(G, sp=1)
89

    
90
    @raises(nx.NetworkXError)
91
    def test_eccentricity_directed_weakly_connected(self):
92
        DG = nx.DiGraph([(1, 2), (1, 3)])
93
        nx.eccentricity(DG)
94

    
95

    
96
class TestResistanceDistance:
97
    @classmethod
98
    def setupClass(cls):
99
        global np
100
        global sp_sparse
101
        try:
102
            import numpy as np
103
        except ImportError:
104
            raise SkipTest('NumPy not available.')
105
        try:
106
            import scipy.sparse as sp_sparse
107
        except ImportError:
108
            raise SkipTest('SciPy Sparse not available.')
109

    
110
    def setUp(self):
111
        G = nx.Graph()
112
        G.add_edge(1, 2, weight=2)
113
        G.add_edge(2, 3, weight=4)
114
        G.add_edge(3, 4, weight=1)
115
        G.add_edge(1, 4, weight=3)
116
        self.G = G
117

    
118
    def test_laplacian_submatrix(self):
119
        from networkx.algorithms.distance_measures import _laplacian_submatrix
120
        M = sp_sparse.csr_matrix([[1, 2, 3],
121
                                     [4, 5, 6],
122
                                     [7, 8, 9]], dtype=np.float32)
123
        N = sp_sparse.csr_matrix([[5, 6],
124
                                     [8, 9]], dtype=np.float32)
125
        Mn, Mn_nodelist = _laplacian_submatrix(1, M, [1, 2, 3])
126
        assert_equal(Mn_nodelist, [2, 3])
127
        assert_true(np.allclose(Mn.toarray(), N.toarray()))
128

    
129
    @raises(nx.NetworkXError)
130
    def test_laplacian_submatrix_square(self):
131
        from networkx.algorithms.distance_measures import _laplacian_submatrix
132
        M = sp_sparse.csr_matrix([[1, 2],
133
                                     [4, 5],
134
                                     [7, 8]], dtype=np.float32)
135
        _laplacian_submatrix(1, M, [1, 2, 3])
136

    
137
    @raises(nx.NetworkXError)
138
    def test_laplacian_submatrix_matrix_node_dim(self):
139
        from networkx.algorithms.distance_measures import _laplacian_submatrix
140
        M = sp_sparse.csr_matrix([[1, 2, 3],
141
                                     [4, 5, 6],
142
                                     [7, 8, 9]], dtype=np.float32)
143
        _laplacian_submatrix(1, M, [1, 2, 3, 4])
144

    
145
    def test_resistance_distance(self):
146
        rd = nx.resistance_distance(self.G, 1, 3, 'weight', True)
147
        test_data = 1/(1/(2+4) + 1/(1+3))
148
        assert_equal(round(rd, 5), round(test_data, 5))
149

    
150
    def test_resistance_distance_noinv(self):
151
        rd = nx.resistance_distance(self.G, 1, 3, 'weight', False)
152
        test_data = 1/(1/(1/2+1/4) + 1/(1/1+1/3))
153
        assert_equal(round(rd, 5), round(test_data, 5))
154

    
155
    def test_resistance_distance_no_weight(self):
156
        rd = nx.resistance_distance(self.G, 1, 3)
157
        assert_equal(round(rd, 5), 1)
158

    
159
    def test_resistance_distance_neg_weight(self):
160
        self.G[2][3]['weight'] = -4
161
        rd = nx.resistance_distance(self.G, 1, 3, 'weight', True)
162
        test_data = 1/(1/(2+-4) + 1/(1+3))
163
        assert_equal(round(rd, 5), round(test_data, 5))
164

    
165
    def test_multigraph(self):
166
        G = nx.MultiGraph()
167
        G.add_edge(1, 2, weight=2)
168
        G.add_edge(2, 3, weight=4)
169
        G.add_edge(3, 4, weight=1)
170
        G.add_edge(1, 4, weight=3)
171
        rd = nx.resistance_distance(G, 1, 3, 'weight', True)
172
        assert_true(np.isclose(rd, 1/(1/(2+4) + 1/(1+3))))
173

    
174
    @raises(ZeroDivisionError)
175
    def test_resistance_distance_div0(self):
176
        self.G[1][2]['weight'] = 0
177
        nx.resistance_distance(self.G, 1, 3, 'weight')
178

    
179
    @raises(nx.NetworkXError)
180
    def test_resistance_distance_not_connected(self):
181
        self.G.add_node(5)
182
        nx.resistance_distance(self.G, 1, 5)
183

    
184
    @raises(nx.NetworkXError)
185
    def test_resistance_distance_same_node(self):
186
        nx.resistance_distance(self.G, 1, 1)
187

    
188
    @raises(nx.NetworkXError)
189
    def test_resistance_distance_nodeA_not_in_graph(self):
190
        nx.resistance_distance(self.G, 9, 1)
191

    
192
    @raises(nx.NetworkXError)
193
    def test_resistance_distance_nodeB_not_in_graph(self):
194
        nx.resistance_distance(self.G, 1, 9)
195

    
196

    
197
class TestBarycenter(object):
198
    """Test :func:`networkx.algorithms.distance_measures.barycenter`."""
199
    def barycenter_as_subgraph(self, g, **kwargs):
200
        """Return the subgraph induced on the barycenter of g"""
201
        b = nx.barycenter(g, **kwargs)
202
        assert_is_instance(b, list)
203
        assert_less_equal(set(b), set(g))
204
        return g.subgraph(b)
205

    
206
    def test_must_be_connected(self):
207
        assert_raises(nx.NetworkXNoPath, nx.barycenter, nx.empty_graph(5))
208

    
209
    def test_sp_kwarg(self):
210
        # Complete graph K_5. Normally it works...
211
        K_5 = nx.complete_graph(5)
212
        sp = dict(nx.shortest_path_length(K_5))
213
        assert_equal(nx.barycenter(K_5, sp=sp), list(K_5))
214

    
215
        # ...but not with the weight argument
216
        for u, v, data in K_5.edges.data():
217
            data['weight'] = 1
218
        assert_raises(ValueError, nx.barycenter, K_5, sp=sp, weight='weight')
219

    
220
        # ...and a corrupted sp can make it seem like K_5 is disconnected
221
        del sp[0][1]
222
        assert_raises(nx.NetworkXNoPath, nx.barycenter, K_5, sp=sp)
223

    
224
    def test_trees(self):
225
        """The barycenter of a tree is a single vertex or an edge.
226

227
        See [West01]_, p. 78.
228
        """
229
        prng = Random(0xdeadbeef)
230
        for i in range(50):
231
            RT = nx.random_tree(prng.randint(1, 75), prng)
232
            b = self.barycenter_as_subgraph(RT)
233
            if len(b) == 2:
234
                assert_equal(b.size(), 1)
235
            else:
236
                assert_equal(len(b), 1)
237
                assert_equal(b.size(), 0)
238

    
239
    def test_this_one_specific_tree(self):
240
        """Test the tree pictured at the bottom of [West01]_, p. 78."""
241
        g = nx.Graph({
242
            'a': ['b'],
243
            'b': ['a', 'x'],
244
            'x': ['b', 'y'],
245
            'y': ['x', 'z'],
246
            'z': ['y', 0, 1, 2, 3, 4],
247
            0: ['z'], 1: ['z'], 2: ['z'], 3: ['z'], 4: ['z']})
248
        b = self.barycenter_as_subgraph(g, attr='barycentricity')
249
        assert_equal(list(b), ['z'])
250
        assert_false(b.edges)
251
        expected_barycentricity = {0: 23, 1: 23, 2: 23, 3: 23, 4: 23,
252
                                   'a': 35, 'b': 27, 'x': 21, 'y': 17, 'z': 15
253
                                   }
254
        for node, barycentricity in expected_barycentricity.items():
255
            assert_equal(g.nodes[node]['barycentricity'], barycentricity)
256

    
257
        # Doubling weights should do nothing but double the barycentricities
258
        for edge in g.edges:
259
            g.edges[edge]['weight'] = 2
260
        b = self.barycenter_as_subgraph(g, weight='weight',
261
                                        attr='barycentricity2')
262
        assert_equal(list(b), ['z'])
263
        assert_false(b.edges)
264
        for node, barycentricity in expected_barycentricity.items():
265
            assert_equal(g.nodes[node]['barycentricity2'], barycentricity*2)