Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (14.9 KB)

1
from __future__ import division
2

    
3
from nose.tools import assert_almost_equal
4
from nose.tools import assert_equal
5
from nose.tools import assert_false
6
from nose.tools import assert_true
7
from nose.tools import assert_raises
8
from nose.tools import ok_
9
from nose.tools import raises
10

    
11
import networkx as nx
12

    
13

    
14
def validate_grid_path(r, c, s, t, p):
15
    ok_(isinstance(p, list))
16
    assert_equal(p[0], s)
17
    assert_equal(p[-1], t)
18
    s = ((s - 1) // c, (s - 1) % c)
19
    t = ((t - 1) // c, (t - 1) % c)
20
    assert_equal(len(p), abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1)
21
    p = [((u - 1) // c, (u - 1) % c) for u in p]
22
    for u in p:
23
        ok_(0 <= u[0] < r)
24
        ok_(0 <= u[1] < c)
25
    for u, v in zip(p[:-1], p[1:]):
26
        ok_((abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)])
27

    
28

    
29
class TestGenericPath:
30

    
31
    def setUp(self):
32
        from networkx import convert_node_labels_to_integers as cnlti
33
        self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1,
34
                          ordering="sorted")
35
        self.cycle = nx.cycle_graph(7)
36
        self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
37
        self.neg_weights = nx.DiGraph()
38
        self.neg_weights.add_edge(0, 1, weight=1)
39
        self.neg_weights.add_edge(0, 2, weight=3)
40
        self.neg_weights.add_edge(1, 3, weight=1)
41
        self.neg_weights.add_edge(2, 3, weight=-2)
42

    
43
    def test_shortest_path(self):
44
        assert_equal(nx.shortest_path(self.cycle, 0, 3), [0, 1, 2, 3])
45
        assert_equal(nx.shortest_path(self.cycle, 0, 4), [0, 6, 5, 4])
46
        validate_grid_path(4, 4, 1, 12, nx.shortest_path(self.grid, 1, 12))
47
        assert_equal(nx.shortest_path(self.directed_cycle, 0, 3), [0, 1, 2, 3])
48
        # now with weights
49
        assert_equal(nx.shortest_path(self.cycle, 0, 3, weight='weight'),
50
                     [0, 1, 2, 3])
51
        assert_equal(nx.shortest_path(self.cycle, 0, 4, weight='weight'),
52
                     [0, 6, 5, 4])
53
        validate_grid_path(4, 4, 1, 12, nx.shortest_path(self.grid, 1, 12,
54
                                                         weight='weight'))
55
        assert_equal(nx.shortest_path(self.directed_cycle, 0, 3,
56
                                      weight='weight'),
57
                     [0, 1, 2, 3])
58
        # weights and method specified
59
        assert_equal(nx.shortest_path(self.directed_cycle, 0, 3,
60
                                      weight='weight', method='dijkstra'),
61
                     [0, 1, 2, 3])
62
        assert_equal(nx.shortest_path(self.directed_cycle, 0, 3,
63
                                      weight='weight', method='bellman-ford'),
64
                     [0, 1, 2, 3])
65
        # when Dijkstra's will probably (depending on precise implementation)
66
        # incorrectly return [0, 1, 3] instead
67
        assert_equal(nx.shortest_path(self.neg_weights, 0, 3, weight='weight',
68
                                      method='bellman-ford'),
69
                     [0, 2, 3])
70
        # confirm bad method rejection
71
        assert_raises(ValueError, nx.shortest_path, self.cycle, method='SPAM')
72
        # confirm absent source rejection
73
        assert_raises(nx.NodeNotFound, nx.shortest_path, self.cycle, 8)
74

    
75
    def test_shortest_path_target(self):
76
        answer = {0: [0, 1], 1: [1], 2: [2, 1]}
77
        sp = nx.shortest_path(nx.path_graph(3), target=1)
78
        assert_equal(sp, answer)
79
        # with weights
80
        sp = nx.shortest_path(nx.path_graph(3), target=1, weight='weight')
81
        assert_equal(sp, answer)
82
        # weights and method specified
83
        sp = nx.shortest_path(nx.path_graph(3), target=1, weight='weight',
84
                              method='dijkstra')
85
        assert_equal(sp, answer)
86
        sp = nx.shortest_path(nx.path_graph(3), target=1, weight='weight',
87
                              method='bellman-ford')
88
        assert_equal(sp, answer)
89

    
90
    def test_shortest_path_length(self):
91
        assert_equal(nx.shortest_path_length(self.cycle, 0, 3), 3)
92
        assert_equal(nx.shortest_path_length(self.grid, 1, 12), 5)
93
        assert_equal(nx.shortest_path_length(self.directed_cycle, 0, 4), 4)
94
        # now with weights
95
        assert_equal(nx.shortest_path_length(self.cycle, 0, 3,
96
                                             weight='weight'),
97
                     3)
98
        assert_equal(nx.shortest_path_length(self.grid, 1, 12,
99
                                             weight='weight'),
100
                     5)
101
        assert_equal(nx.shortest_path_length(self.directed_cycle, 0, 4,
102
                                             weight='weight'),
103
                     4)
104
        # weights and method specified
105
        assert_equal(nx.shortest_path_length(self.cycle, 0, 3, weight='weight',
106
                                             method='dijkstra'),
107
                     3)
108
        assert_equal(nx.shortest_path_length(self.cycle, 0, 3, weight='weight',
109
                                             method='bellman-ford'),
110
                     3)
111
        # confirm bad method rejection
112
        assert_raises(ValueError,
113
                      nx.shortest_path_length,
114
                      self.cycle,
115
                      method='SPAM')
116
        # confirm absent source rejection
117
        assert_raises(nx.NodeNotFound, nx.shortest_path_length, self.cycle, 8)
118

    
119
    def test_shortest_path_length_target(self):
120
        answer = {0: 1, 1: 0, 2: 1}
121
        sp = dict(nx.shortest_path_length(nx.path_graph(3), target=1))
122
        assert_equal(sp, answer)
123
        # with weights
124
        sp = nx.shortest_path_length(nx.path_graph(3), target=1,
125
                                     weight='weight')
126
        assert_equal(sp, answer)
127
        # weights and method specified
128
        sp = nx.shortest_path_length(nx.path_graph(3), target=1,
129
                                     weight='weight', method='dijkstra')
130
        assert_equal(sp, answer)
131
        sp = nx.shortest_path_length(nx.path_graph(3), target=1,
132
                                     weight='weight', method='bellman-ford')
133
        assert_equal(sp, answer)
134

    
135
    def test_single_source_shortest_path(self):
136
        p = nx.shortest_path(self.cycle, 0)
137
        assert_equal(p[3], [0, 1, 2, 3])
138
        assert_equal(p, nx.single_source_shortest_path(self.cycle, 0))
139
        p = nx.shortest_path(self.grid, 1)
140
        validate_grid_path(4, 4, 1, 12, p[12])
141
        # now with weights
142
        p = nx.shortest_path(self.cycle, 0, weight='weight')
143
        assert_equal(p[3], [0, 1, 2, 3])
144
        assert_equal(p, nx.single_source_dijkstra_path(self.cycle, 0))
145
        p = nx.shortest_path(self.grid, 1, weight='weight')
146
        validate_grid_path(4, 4, 1, 12, p[12])
147
        # weights and method specified
148
        p = nx.shortest_path(self.cycle, 0, method='dijkstra', weight='weight')
149
        assert_equal(p[3], [0, 1, 2, 3])
150
        assert_equal(p, nx.single_source_shortest_path(self.cycle, 0))
151
        p = nx.shortest_path(self.cycle, 0, method='bellman-ford',
152
                             weight='weight')
153
        assert_equal(p[3], [0, 1, 2, 3])
154
        assert_equal(p, nx.single_source_shortest_path(self.cycle, 0))
155

    
156
    def test_single_source_shortest_path_length(self):
157
        ans = dict(nx.shortest_path_length(self.cycle, 0))
158
        assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
159
        assert_equal(ans,
160
                     dict(nx.single_source_shortest_path_length(self.cycle,
161
                                                                0)))
162
        ans = dict(nx.shortest_path_length(self.grid, 1))
163
        assert_equal(ans[16], 6)
164
        # now with weights
165
        ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight'))
166
        assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
167
        assert_equal(ans, dict(nx.single_source_dijkstra_path_length(
168
            self.cycle, 0)))
169
        ans = dict(nx.shortest_path_length(self.grid, 1, weight='weight'))
170
        assert_equal(ans[16], 6)
171
        # weights and method specified
172
        ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight',
173
                                           method='dijkstra'))
174
        assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
175
        assert_equal(ans, dict(nx.single_source_dijkstra_path_length(
176
            self.cycle, 0)))
177
        ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight',
178
                                           method='bellman-ford'))
179
        assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
180
        assert_equal(ans, dict(nx.single_source_bellman_ford_path_length(
181
            self.cycle, 0)))
182

    
183
    def test_all_pairs_shortest_path(self):
184
        p = nx.shortest_path(self.cycle)
185
        assert_equal(p[0][3], [0, 1, 2, 3])
186
        assert_equal(p, dict(nx.all_pairs_shortest_path(self.cycle)))
187
        p = nx.shortest_path(self.grid)
188
        validate_grid_path(4, 4, 1, 12, p[1][12])
189
        # now with weights
190
        p = nx.shortest_path(self.cycle, weight='weight')
191
        assert_equal(p[0][3], [0, 1, 2, 3])
192
        assert_equal(p, dict(nx.all_pairs_dijkstra_path(self.cycle)))
193
        p = nx.shortest_path(self.grid, weight='weight')
194
        validate_grid_path(4, 4, 1, 12, p[1][12])
195
        # weights and method specified
196
        p = nx.shortest_path(self.cycle, weight='weight', method='dijkstra')
197
        assert_equal(p[0][3], [0, 1, 2, 3])
198
        assert_equal(p, dict(nx.all_pairs_dijkstra_path(self.cycle)))
199
        p = nx.shortest_path(self.cycle, weight='weight',
200
                             method='bellman-ford')
201
        assert_equal(p[0][3], [0, 1, 2, 3])
202
        assert_equal(p, dict(nx.all_pairs_bellman_ford_path(self.cycle)))
203

    
204
    def test_all_pairs_shortest_path_length(self):
205
        ans = dict(nx.shortest_path_length(self.cycle))
206
        assert_equal(ans[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
207
        assert_equal(ans, dict(nx.all_pairs_shortest_path_length(self.cycle)))
208
        ans = dict(nx.shortest_path_length(self.grid))
209
        assert_equal(ans[1][16], 6)
210
        # now with weights
211
        ans = dict(nx.shortest_path_length(self.cycle, weight='weight'))
212
        assert_equal(ans[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
213
        assert_equal(ans, dict(nx.all_pairs_dijkstra_path_length(self.cycle)))
214
        ans = dict(nx.shortest_path_length(self.grid, weight='weight'))
215
        assert_equal(ans[1][16], 6)
216
        # weights and method specified
217
        ans = dict(nx.shortest_path_length(self.cycle, weight='weight',
218
                                           method='dijkstra'))
219
        assert_equal(ans[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
220
        assert_equal(ans, dict(nx.all_pairs_dijkstra_path_length(self.cycle)))
221
        ans = dict(nx.shortest_path_length(self.cycle, weight='weight',
222
                                           method='bellman-ford'))
223
        assert_equal(ans[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
224
        assert_equal(ans,
225
                     dict(nx.all_pairs_bellman_ford_path_length(self.cycle)))
226

    
227
    def test_has_path(self):
228
        G = nx.Graph()
229
        nx.add_path(G, range(3))
230
        nx.add_path(G, range(3, 5))
231
        assert_true(nx.has_path(G, 0, 2))
232
        assert_false(nx.has_path(G, 0, 4))
233

    
234
    def test_all_shortest_paths(self):
235
        G = nx.Graph()
236
        nx.add_path(G, [0, 1, 2, 3])
237
        nx.add_path(G, [0, 10, 20, 3])
238
        assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
239
                     sorted(nx.all_shortest_paths(G, 0, 3)))
240
        # with weights
241
        G = nx.Graph()
242
        nx.add_path(G, [0, 1, 2, 3])
243
        nx.add_path(G, [0, 10, 20, 3])
244
        assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
245
                     sorted(nx.all_shortest_paths(G, 0, 3, weight='weight')))
246
        # weights and method specified
247
        G = nx.Graph()
248
        nx.add_path(G, [0, 1, 2, 3])
249
        nx.add_path(G, [0, 10, 20, 3])
250
        assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
251
                     sorted(nx.all_shortest_paths(G, 0, 3, weight='weight',
252
                                                  method='dijkstra')))
253
        G = nx.Graph()
254
        nx.add_path(G, [0, 1, 2, 3])
255
        nx.add_path(G, [0, 10, 20, 3])
256
        assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
257
                     sorted(nx.all_shortest_paths(G, 0, 3, weight='weight',
258
                                                  method='bellman-ford')))
259

    
260
    @raises(nx.NetworkXNoPath)
261
    def test_all_shortest_paths_raise(self):
262
        G = nx.path_graph(4)
263
        G.add_node(4)
264
        list(nx.all_shortest_paths(G, 0, 4))
265

    
266
    @raises(ValueError)
267
    def test_bad_method(self):
268
        G = nx.path_graph(2)
269
        list(nx.all_shortest_paths(G, 0, 1, weight='weight', method='SPAM'))
270

    
271

    
272
class TestAverageShortestPathLength(object):
273

    
274
    def test_cycle_graph(self):
275
        ans = nx.average_shortest_path_length(nx.cycle_graph(7))
276
        assert_almost_equal(ans, 2)
277

    
278
    def test_path_graph(self):
279
        ans = nx.average_shortest_path_length(nx.path_graph(5))
280
        assert_almost_equal(ans, 2)
281

    
282
    def test_weighted(self):
283
        G = nx.Graph()
284
        nx.add_cycle(G, range(7), weight=2)
285
        ans = nx.average_shortest_path_length(G, weight='weight')
286
        assert_almost_equal(ans, 4)
287
        G = nx.Graph()
288
        nx.add_path(G, range(5), weight=2)
289
        ans = nx.average_shortest_path_length(G, weight='weight')
290
        assert_almost_equal(ans, 4)
291

    
292
    def test_specified_methods(self):
293
        G = nx.Graph()
294
        nx.add_cycle(G, range(7), weight=2)
295
        ans = nx.average_shortest_path_length(G,
296
                                              weight='weight',
297
                                              method='dijkstra')
298
        assert_almost_equal(ans, 4)
299
        ans = nx.average_shortest_path_length(G,
300
                                              weight='weight',
301
                                              method='bellman-ford')
302
        assert_almost_equal(ans, 4)
303
        G = nx.Graph()
304
        nx.add_path(G, range(5), weight=2)
305
        ans = nx.average_shortest_path_length(G,
306
                                              weight='weight',
307
                                              method='dijkstra')
308
        assert_almost_equal(ans, 4)
309
        ans = nx.average_shortest_path_length(G,
310
                                              weight='weight',
311
                                              method='bellman-ford')
312
        assert_almost_equal(ans, 4)
313

    
314
    def test_disconnected(self):
315
        g = nx.Graph()
316
        g.add_nodes_from(range(3))
317
        g.add_edge(0, 1)
318
        assert_raises(nx.NetworkXError, nx.average_shortest_path_length, g)
319
        g = g.to_directed()
320
        assert_raises(nx.NetworkXError, nx.average_shortest_path_length, g)
321

    
322
    def test_trivial_graph(self):
323
        """Tests that the trivial graph has average path length zero,
324
        since there is exactly one path of length zero in the trivial
325
        graph.
326

327
        For more information, see issue #1960.
328

329
        """
330
        G = nx.trivial_graph()
331
        assert_equal(nx.average_shortest_path_length(G), 0)
332

    
333
    @raises(nx.NetworkXPointlessConcept)
334
    def test_null_graph(self):
335
        nx.average_shortest_path_length(nx.null_graph())
336

    
337
    @raises(ValueError)
338
    def test_bad_method(self):
339
        G = nx.path_graph(2)
340
        nx.average_shortest_path_length(G, weight='weight', method='SPAM')