Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (18.1 KB)

1
# -*- coding: utf-8 -*-
2

    
3
import networkx as nx
4
from nose.tools import assert_equal, assert_raises
5
import os
6

    
7

    
8
class TestMinCostFlow:
9
    def test_simple_digraph(self):
10
        G = nx.DiGraph()
11
        G.add_node('a', demand=-5)
12
        G.add_node('d', demand=5)
13
        G.add_edge('a', 'b', weight=3, capacity=4)
14
        G.add_edge('a', 'c', weight=6, capacity=10)
15
        G.add_edge('b', 'd', weight=1, capacity=9)
16
        G.add_edge('c', 'd', weight=2, capacity=5)
17
        flowCost, H = nx.network_simplex(G)
18
        soln = {'a': {'b': 4, 'c': 1},
19
                'b': {'d': 4},
20
                'c': {'d': 1},
21
                'd': {}}
22
        assert_equal(flowCost, 24)
23
        assert_equal(nx.min_cost_flow_cost(G), 24)
24
        assert_equal(H, soln)
25
        assert_equal(nx.min_cost_flow(G), soln)
26
        assert_equal(nx.cost_of_flow(G, H), 24)
27

    
28
        flowCost, H = nx.capacity_scaling(G)
29
        assert_equal(flowCost, 24)
30
        assert_equal(nx.cost_of_flow(G, H), 24)
31
        assert_equal(H, soln)
32

    
33
    def test_negcycle_infcap(self):
34
        G = nx.DiGraph()
35
        G.add_node('s', demand=-5)
36
        G.add_node('t', demand=5)
37
        G.add_edge('s', 'a', weight=1, capacity=3)
38
        G.add_edge('a', 'b', weight=3)
39
        G.add_edge('c', 'a', weight=-6)
40
        G.add_edge('b', 'd', weight=1)
41
        G.add_edge('d', 'c', weight=-2)
42
        G.add_edge('d', 't', weight=1, capacity=3)
43
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
44
        assert_raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
45

    
46
    def test_sum_demands_not_zero(self):
47
        G = nx.DiGraph()
48
        G.add_node('s', demand=-5)
49
        G.add_node('t', demand=4)
50
        G.add_edge('s', 'a', weight=1, capacity=3)
51
        G.add_edge('a', 'b', weight=3)
52
        G.add_edge('a', 'c', weight=-6)
53
        G.add_edge('b', 'd', weight=1)
54
        G.add_edge('c', 'd', weight=-2)
55
        G.add_edge('d', 't', weight=1, capacity=3)
56
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
57
        assert_raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
58

    
59
    def test_no_flow_satisfying_demands(self):
60
        G = nx.DiGraph()
61
        G.add_node('s', demand=-5)
62
        G.add_node('t', demand=5)
63
        G.add_edge('s', 'a', weight=1, capacity=3)
64
        G.add_edge('a', 'b', weight=3)
65
        G.add_edge('a', 'c', weight=-6)
66
        G.add_edge('b', 'd', weight=1)
67
        G.add_edge('c', 'd', weight=-2)
68
        G.add_edge('d', 't', weight=1, capacity=3)
69
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
70
        assert_raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
71

    
72
    def test_transshipment(self):
73
        G = nx.DiGraph()
74
        G.add_node('a', demand=1)
75
        G.add_node('b', demand=-2)
76
        G.add_node('c', demand=-2)
77
        G.add_node('d', demand=3)
78
        G.add_node('e', demand=-4)
79
        G.add_node('f', demand=-4)
80
        G.add_node('g', demand=3)
81
        G.add_node('h', demand=2)
82
        G.add_node('r', demand=3)
83
        G.add_edge('a', 'c', weight=3)
84
        G.add_edge('r', 'a', weight=2)
85
        G.add_edge('b', 'a', weight=9)
86
        G.add_edge('r', 'c', weight=0)
87
        G.add_edge('b', 'r', weight=-6)
88
        G.add_edge('c', 'd', weight=5)
89
        G.add_edge('e', 'r', weight=4)
90
        G.add_edge('e', 'f', weight=3)
91
        G.add_edge('h', 'b', weight=4)
92
        G.add_edge('f', 'd', weight=7)
93
        G.add_edge('f', 'h', weight=12)
94
        G.add_edge('g', 'd', weight=12)
95
        G.add_edge('f', 'g', weight=-1)
96
        G.add_edge('h', 'g', weight=-10)
97
        flowCost, H = nx.network_simplex(G)
98
        soln = {'a': {'c': 0},
99
                'b': {'a': 0, 'r': 2},
100
                'c': {'d': 3},
101
                'd': {},
102
                'e': {'r': 3, 'f': 1},
103
                'f': {'d': 0, 'g': 3, 'h': 2},
104
                'g': {'d': 0},
105
                'h': {'b': 0, 'g': 0},
106
                'r': {'a': 1, 'c': 1}}
107
        assert_equal(flowCost, 41)
108
        assert_equal(nx.min_cost_flow_cost(G), 41)
109
        assert_equal(H, soln)
110
        assert_equal(nx.min_cost_flow(G), soln)
111
        assert_equal(nx.cost_of_flow(G, H), 41)
112

    
113
        flowCost, H = nx.capacity_scaling(G)
114
        assert_equal(flowCost, 41)
115
        assert_equal(nx.cost_of_flow(G, H), 41)
116
        assert_equal(H, soln)
117

    
118
    def test_max_flow_min_cost(self):
119
        G = nx.DiGraph()
120
        G.add_edge('s', 'a', bandwidth=6)
121
        G.add_edge('s', 'c', bandwidth=10, cost=10)
122
        G.add_edge('a', 'b', cost=6)
123
        G.add_edge('b', 'd', bandwidth=8, cost=7)
124
        G.add_edge('c', 'd', cost=10)
125
        G.add_edge('d', 't', bandwidth=5, cost=5)
126
        soln = {'s': {'a': 5, 'c': 0},
127
                'a': {'b': 5},
128
                'b': {'d': 5},
129
                'c': {'d': 0},
130
                'd': {'t': 5},
131
                't': {}}
132
        flow = nx.max_flow_min_cost(G, 's', 't', capacity='bandwidth',
133
                                    weight='cost')
134
        assert_equal(flow, soln)
135
        assert_equal(nx.cost_of_flow(G, flow, weight='cost'), 90)
136

    
137
        G.add_edge('t', 's', cost=-100)
138
        flowCost, flow = nx.capacity_scaling(G, capacity='bandwidth',
139
                                             weight='cost')
140
        G.remove_edge('t', 's')
141
        assert_equal(flowCost, -410)
142
        assert_equal(flow['t']['s'], 5)
143
        del flow['t']['s']
144
        assert_equal(flow, soln)
145
        assert_equal(nx.cost_of_flow(G, flow, weight='cost'), 90)
146

    
147
    def test_digraph1(self):
148
        # From Bradley, S. P., Hax, A. C. and Magnanti, T. L. Applied
149
        # Mathematical Programming. Addison-Wesley, 1977.
150
        G = nx.DiGraph()
151
        G.add_node(1, demand=-20)
152
        G.add_node(4, demand=5)
153
        G.add_node(5, demand=15)
154
        G.add_edges_from([(1, 2, {'capacity': 15, 'weight': 4}),
155
                          (1, 3, {'capacity': 8, 'weight': 4}),
156
                          (2, 3, {'weight': 2}),
157
                          (2, 4, {'capacity': 4, 'weight': 2}),
158
                          (2, 5, {'capacity': 10, 'weight': 6}),
159
                          (3, 4, {'capacity': 15, 'weight': 1}),
160
                          (3, 5, {'capacity': 5, 'weight': 3}),
161
                          (4, 5, {'weight': 2}),
162
                          (5, 3, {'capacity': 4, 'weight': 1})])
163
        flowCost, H = nx.network_simplex(G)
164
        soln = {1: {2: 12, 3: 8},
165
                2: {3: 8, 4: 4, 5: 0},
166
                3: {4: 11, 5: 5},
167
                4: {5: 10},
168
                5: {3: 0}}
169
        assert_equal(flowCost, 150)
170
        assert_equal(nx.min_cost_flow_cost(G), 150)
171
        assert_equal(H, soln)
172
        assert_equal(nx.min_cost_flow(G), soln)
173
        assert_equal(nx.cost_of_flow(G, H), 150)
174

    
175
        flowCost, H = nx.capacity_scaling(G)
176
        assert_equal(flowCost, 150)
177
        assert_equal(H, soln)
178
        assert_equal(nx.cost_of_flow(G, H), 150)
179

    
180
    def test_digraph2(self):
181
        # Example from ticket #430 from mfrasca. Original source:
182
        # http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/mincost.4up.pdf, slide 11.
183
        G = nx.DiGraph()
184
        G.add_edge('s', 1, capacity=12)
185
        G.add_edge('s', 2, capacity=6)
186
        G.add_edge('s', 3, capacity=14)
187
        G.add_edge(1, 2, capacity=11, weight=4)
188
        G.add_edge(2, 3, capacity=9, weight=6)
189
        G.add_edge(1, 4, capacity=5, weight=5)
190
        G.add_edge(1, 5, capacity=2, weight=12)
191
        G.add_edge(2, 5, capacity=4, weight=4)
192
        G.add_edge(2, 6, capacity=2, weight=6)
193
        G.add_edge(3, 6, capacity=31, weight=3)
194
        G.add_edge(4, 5, capacity=18, weight=4)
195
        G.add_edge(5, 6, capacity=9, weight=5)
196
        G.add_edge(4, 't', capacity=3)
197
        G.add_edge(5, 't', capacity=7)
198
        G.add_edge(6, 't', capacity=22)
199
        flow = nx.max_flow_min_cost(G, 's', 't')
200
        soln = {1: {2: 6, 4: 5, 5: 1},
201
                2: {3: 6, 5: 4, 6: 2},
202
                3: {6: 20},
203
                4: {5: 2, 't': 3},
204
                5: {6: 0, 't': 7},
205
                6: {'t': 22},
206
                's': {1: 12, 2: 6, 3: 14},
207
                't': {}}
208
        assert_equal(flow, soln)
209

    
210
        G.add_edge('t', 's', weight=-100)
211
        flowCost, flow = nx.capacity_scaling(G)
212
        G.remove_edge('t', 's')
213
        assert_equal(flow['t']['s'], 32)
214
        assert_equal(flowCost, -3007)
215
        del flow['t']['s']
216
        assert_equal(flow, soln)
217
        assert_equal(nx.cost_of_flow(G, flow), 193)
218

    
219
    def test_digraph3(self):
220
        """Combinatorial Optimization: Algorithms and Complexity,
221
        Papadimitriou Steiglitz at page 140 has an example, 7.1, but that
222
        admits multiple solutions, so I alter it a bit. From ticket #430
223
        by mfrasca."""
224

    
225
        G = nx.DiGraph()
226
        G.add_edge('s', 'a')
227
        G['s']['a'].update({0: 2, 1: 4})
228
        G.add_edge('s', 'b')
229
        G['s']['b'].update({0: 2, 1: 1})
230
        G.add_edge('a', 'b')
231
        G['a']['b'].update({0: 5, 1: 2})
232
        G.add_edge('a', 't')
233
        G['a']['t'].update({0: 1, 1: 5})
234
        G.add_edge('b', 'a')
235
        G['b']['a'].update({0: 1, 1: 3})
236
        G.add_edge('b', 't')
237
        G['b']['t'].update({0: 3, 1: 2})
238

    
239
        "PS.ex.7.1: testing main function"
240
        sol = nx.max_flow_min_cost(G, 's', 't', capacity=0, weight=1)
241
        flow = sum(v for v in sol['s'].values())
242
        assert_equal(4, flow)
243
        assert_equal(23, nx.cost_of_flow(G, sol, weight=1))
244
        assert_equal(sol['s'], {'a': 2, 'b': 2})
245
        assert_equal(sol['a'], {'b': 1, 't': 1})
246
        assert_equal(sol['b'], {'a': 0, 't': 3})
247
        assert_equal(sol['t'], {})
248

    
249
        G.add_edge('t', 's')
250
        G['t']['s'].update({1: -100})
251
        flowCost, sol = nx.capacity_scaling(G, capacity=0, weight=1)
252
        G.remove_edge('t', 's')
253
        flow = sum(v for v in sol['s'].values())
254
        assert_equal(4, flow)
255
        assert_equal(sol['t']['s'], 4)
256
        assert_equal(flowCost, -377)
257
        del sol['t']['s']
258
        assert_equal(sol['s'], {'a': 2, 'b': 2})
259
        assert_equal(sol['a'], {'b': 1, 't': 1})
260
        assert_equal(sol['b'], {'a': 0, 't': 3})
261
        assert_equal(sol['t'], {})
262
        assert_equal(nx.cost_of_flow(G, sol, weight=1), 23)
263

    
264
    def test_zero_capacity_edges(self):
265
        """Address issue raised in ticket #617 by arv."""
266
        G = nx.DiGraph()
267
        G.add_edges_from([(1, 2, {'capacity': 1, 'weight': 1}),
268
                          (1, 5, {'capacity': 1, 'weight': 1}),
269
                          (2, 3, {'capacity': 0, 'weight': 1}),
270
                          (2, 5, {'capacity': 1, 'weight': 1}),
271
                          (5, 3, {'capacity': 2, 'weight': 1}),
272
                          (5, 4, {'capacity': 0, 'weight': 1}),
273
                          (3, 4, {'capacity': 2, 'weight': 1})])
274
        G.nodes[1]['demand'] = -1
275
        G.nodes[2]['demand'] = -1
276
        G.nodes[4]['demand'] = 2
277

    
278
        flowCost, H = nx.network_simplex(G)
279
        soln = {1: {2: 0, 5: 1},
280
                2: {3: 0, 5: 1},
281
                3: {4: 2},
282
                4: {},
283
                5: {3: 2, 4: 0}}
284
        assert_equal(flowCost, 6)
285
        assert_equal(nx.min_cost_flow_cost(G), 6)
286
        assert_equal(H, soln)
287
        assert_equal(nx.min_cost_flow(G), soln)
288
        assert_equal(nx.cost_of_flow(G, H), 6)
289

    
290
        flowCost, H = nx.capacity_scaling(G)
291
        assert_equal(flowCost, 6)
292
        assert_equal(H, soln)
293
        assert_equal(nx.cost_of_flow(G, H), 6)
294

    
295
    def test_digon(self):
296
        """Check if digons are handled properly. Taken from ticket
297
        #618 by arv."""
298
        nodes = [(1, {}),
299
                 (2, {'demand': -4}),
300
                 (3, {'demand': 4}),
301
                 ]
302
        edges = [(1, 2, {'capacity': 3, 'weight': 600000}),
303
                 (2, 1, {'capacity': 2, 'weight': 0}),
304
                 (2, 3, {'capacity': 5, 'weight': 714285}),
305
                 (3, 2, {'capacity': 2, 'weight': 0}),
306
                 ]
307
        G = nx.DiGraph(edges)
308
        G.add_nodes_from(nodes)
309
        flowCost, H = nx.network_simplex(G)
310
        soln = {1: {2: 0},
311
                2: {1: 0, 3: 4},
312
                3: {2: 0}}
313
        assert_equal(flowCost, 2857140)
314
        assert_equal(nx.min_cost_flow_cost(G), 2857140)
315
        assert_equal(H, soln)
316
        assert_equal(nx.min_cost_flow(G), soln)
317
        assert_equal(nx.cost_of_flow(G, H), 2857140)
318

    
319
        flowCost, H = nx.capacity_scaling(G)
320
        assert_equal(flowCost, 2857140)
321
        assert_equal(H, soln)
322
        assert_equal(nx.cost_of_flow(G, H), 2857140)
323

    
324
    def test_deadend(self):
325
        """Check if one-node cycles are handled properly. Taken from ticket
326
        #2906 from @sshraven."""
327
        G = nx.DiGraph()
328

    
329
        G.add_nodes_from(range(5), demand=0)
330
        G.node[4]['demand'] = -13
331
        G.node[3]['demand'] = 13
332

    
333
        G.add_edges_from([(0,2), (0, 3), (2, 1)], capacity=20, weight=0.1)
334
        assert_raises(nx.NetworkXUnfeasible, nx.min_cost_flow, G)
335

    
336
    def test_infinite_capacity_neg_digon(self):
337
        """An infinite capacity negative cost digon results in an unbounded
338
        instance."""
339
        nodes = [(1, {}),
340
                 (2, {'demand': -4}),
341
                 (3, {'demand': 4}),
342
                 ]
343
        edges = [(1, 2, {'weight': -600}),
344
                 (2, 1, {'weight': 0}),
345
                 (2, 3, {'capacity': 5, 'weight': 714285}),
346
                 (3, 2, {'capacity': 2, 'weight': 0}),
347
                 ]
348
        G = nx.DiGraph(edges)
349
        G.add_nodes_from(nodes)
350
        assert_raises(nx.NetworkXUnbounded, nx.network_simplex, G)
351
        assert_raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
352

    
353
    def test_finite_capacity_neg_digon(self):
354
        """The digon should receive the maximum amount of flow it can handle.
355
        Taken from ticket #749 by @chuongdo."""
356
        G = nx.DiGraph()
357
        G.add_edge('a', 'b', capacity=1, weight=-1)
358
        G.add_edge('b', 'a', capacity=1, weight=-1)
359
        min_cost = -2
360
        assert_equal(nx.min_cost_flow_cost(G), min_cost)
361

    
362
        flowCost, H = nx.capacity_scaling(G)
363
        assert_equal(flowCost, -2)
364
        assert_equal(H, {'a': {'b': 1}, 'b': {'a': 1}})
365
        assert_equal(nx.cost_of_flow(G, H), -2)
366

    
367
    def test_multidigraph(self):
368
        """Multidigraphs are acceptable."""
369
        G = nx.MultiDiGraph()
370
        G.add_weighted_edges_from([(1, 2, 1), (2, 3, 2)], weight='capacity')
371
        flowCost, H = nx.network_simplex(G)
372
        assert_equal(flowCost, 0)
373
        assert_equal(H, {1: {2: {0: 0}}, 2: {3: {0: 0}}, 3: {}})
374

    
375
        flowCost, H = nx.capacity_scaling(G)
376
        assert_equal(flowCost, 0)
377
        assert_equal(H, {1: {2: {0: 0}}, 2: {3: {0: 0}}, 3: {}})
378

    
379
    def test_negative_selfloops(self):
380
        """Negative selfloops should cause an exception if uncapacitated and
381
        always be saturated otherwise.
382
        """
383
        G = nx.DiGraph()
384
        G.add_edge(1, 1, weight=-1)
385
        assert_raises(nx.NetworkXUnbounded, nx.network_simplex, G)
386
        assert_raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
387
        G[1][1]['capacity'] = 2
388
        flowCost, H = nx.network_simplex(G)
389
        assert_equal(flowCost, -2)
390
        assert_equal(H, {1: {1: 2}})
391
        flowCost, H = nx.capacity_scaling(G)
392
        assert_equal(flowCost, -2)
393
        assert_equal(H, {1: {1: 2}})
394

    
395
        G = nx.MultiDiGraph()
396
        G.add_edge(1, 1, 'x', weight=-1)
397
        G.add_edge(1, 1, 'y', weight=1)
398
        assert_raises(nx.NetworkXUnbounded, nx.network_simplex, G)
399
        assert_raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
400
        G[1][1]['x']['capacity'] = 2
401
        flowCost, H = nx.network_simplex(G)
402
        assert_equal(flowCost, -2)
403
        assert_equal(H, {1: {1: {'x': 2, 'y': 0}}})
404
        flowCost, H = nx.capacity_scaling(G)
405
        assert_equal(flowCost, -2)
406
        assert_equal(H, {1: {1: {'x': 2, 'y': 0}}})
407

    
408
    def test_bone_shaped(self):
409
        # From #1283
410
        G = nx.DiGraph()
411
        G.add_node(0, demand=-4)
412
        G.add_node(1, demand=2)
413
        G.add_node(2, demand=2)
414
        G.add_node(3, demand=4)
415
        G.add_node(4, demand=-2)
416
        G.add_node(5, demand=-2)
417
        G.add_edge(0, 1, capacity=4)
418
        G.add_edge(0, 2, capacity=4)
419
        G.add_edge(4, 3, capacity=4)
420
        G.add_edge(5, 3, capacity=4)
421
        G.add_edge(0, 3, capacity=0)
422
        flowCost, H = nx.network_simplex(G)
423
        assert_equal(flowCost, 0)
424
        assert_equal(
425
            H, {0: {1: 2, 2: 2, 3: 0}, 1: {}, 2: {}, 3: {}, 4: {3: 2}, 5: {3: 2}})
426
        flowCost, H = nx.capacity_scaling(G)
427
        assert_equal(flowCost, 0)
428
        assert_equal(
429
            H, {0: {1: 2, 2: 2, 3: 0}, 1: {}, 2: {}, 3: {}, 4: {3: 2}, 5: {3: 2}})
430

    
431
    def test_exceptions(self):
432
        G = nx.Graph()
433
        assert_raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
434
        assert_raises(nx.NetworkXNotImplemented, nx.capacity_scaling, G)
435
        G = nx.MultiGraph()
436
        assert_raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
437
        assert_raises(nx.NetworkXNotImplemented, nx.capacity_scaling, G)
438
        G = nx.DiGraph()
439
        assert_raises(nx.NetworkXError, nx.network_simplex, G)
440
        assert_raises(nx.NetworkXError, nx.capacity_scaling, G)
441
        G.add_node(0, demand=float('inf'))
442
        assert_raises(nx.NetworkXError, nx.network_simplex, G)
443
        assert_raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
444
        G.nodes[0]['demand'] = 0
445
        G.add_node(1, demand=0)
446
        G.add_edge(0, 1, weight=-float('inf'))
447
        assert_raises(nx.NetworkXError, nx.network_simplex, G)
448
        assert_raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
449
        G[0][1]['weight'] = 0
450
        G.add_edge(0, 0, weight=float('inf'))
451
        assert_raises(nx.NetworkXError, nx.network_simplex, G)
452
        #assert_raises(nx.NetworkXError, nx.capacity_scaling, G)
453
        G[0][0]['weight'] = 0
454
        G[0][1]['capacity'] = -1
455
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
456
        #assert_raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
457
        G[0][1]['capacity'] = 0
458
        G[0][0]['capacity'] = -1
459
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
460
        #assert_raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
461

    
462
    def test_large(self):
463
        fname = os.path.join(os.path.dirname(__file__), 'netgen-2.gpickle.bz2')
464
        G = nx.read_gpickle(fname)
465
        flowCost, flowDict = nx.network_simplex(G)
466
        assert_equal(6749969302, flowCost)
467
        assert_equal(6749969302, nx.cost_of_flow(G, flowDict))
468
        flowCost, flowDict = nx.capacity_scaling(G)
469
        assert_equal(6749969302, flowCost)
470
        assert_equal(6749969302, nx.cost_of_flow(G, flowDict))