Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (18.4 KB)

1
# -*- coding: utf-8 -*-
2
"""Maximum flow algorithms test suite.
3
"""
4
from nose.tools import *
5

    
6
import networkx as nx
7
from networkx.algorithms.flow import build_flow_dict, build_residual_network
8
from networkx.algorithms.flow import boykov_kolmogorov
9
from networkx.algorithms.flow import edmonds_karp
10
from networkx.algorithms.flow import preflow_push
11
from networkx.algorithms.flow import shortest_augmenting_path
12
from networkx.algorithms.flow import dinitz
13

    
14
flow_funcs = [boykov_kolmogorov, dinitz, edmonds_karp, preflow_push, shortest_augmenting_path]
15
max_min_funcs = [nx.maximum_flow, nx.minimum_cut]
16
flow_value_funcs = [nx.maximum_flow_value, nx.minimum_cut_value]
17
interface_funcs = sum([max_min_funcs, flow_value_funcs], [])
18
all_funcs = sum([flow_funcs, interface_funcs], [])
19

    
20
msg = "Assertion failed in function: {0}"
21
msgi = "Assertion failed in function: {0} in interface {1}"
22

    
23

    
24
def compute_cutset(G, partition):
25
    reachable, non_reachable = partition
26
    cutset = set()
27
    for u, nbrs in ((n, G[n]) for n in reachable):
28
        cutset.update((u, v) for v in nbrs if v in non_reachable)
29
    return cutset
30

    
31

    
32
def validate_flows(G, s, t, flowDict, solnValue, capacity, flow_func):
33
    assert_equal(set(G), set(flowDict), msg=msg.format(flow_func.__name__))
34
    for u in G:
35
        assert_equal(set(G[u]), set(flowDict[u]),
36
                     msg=msg.format(flow_func.__name__))
37
    excess = {u: 0 for u in flowDict}
38
    for u in flowDict:
39
        for v, flow in flowDict[u].items():
40
            if capacity in G[u][v]:
41
                ok_(flow <= G[u][v][capacity])
42
            ok_(flow >= 0, msg=msg.format(flow_func.__name__))
43
            excess[u] -= flow
44
            excess[v] += flow
45
    for u, exc in excess.items():
46
        if u == s:
47
            assert_equal(exc, -solnValue, msg=msg.format(flow_func.__name__))
48
        elif u == t:
49
            assert_equal(exc, solnValue, msg=msg.format(flow_func.__name__))
50
        else:
51
            assert_equal(exc, 0, msg=msg.format(flow_func.__name__))
52

    
53

    
54
def validate_cuts(G, s, t, solnValue, partition, capacity, flow_func):
55
    assert_true(all(n in G for n in partition[0]),
56
                msg=msg.format(flow_func.__name__))
57
    assert_true(all(n in G for n in partition[1]),
58
                msg=msg.format(flow_func.__name__))
59
    cutset = compute_cutset(G, partition)
60
    assert_true(all(G.has_edge(u, v) for (u, v) in cutset),
61
                msg=msg.format(flow_func.__name__))
62
    assert_equal(solnValue, sum(G[u][v][capacity] for (u, v) in cutset),
63
                 msg=msg.format(flow_func.__name__))
64
    H = G.copy()
65
    H.remove_edges_from(cutset)
66
    if not G.is_directed():
67
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
68
    else:
69
        assert_false(nx.is_strongly_connected(H),
70
                     msg=msg.format(flow_func.__name__))
71

    
72

    
73
def compare_flows_and_cuts(G, s, t, solnFlows, solnValue, capacity='capacity'):
74
    for flow_func in flow_funcs:
75
        R = flow_func(G, s, t, capacity)
76
        # Test both legacy and new implementations.
77
        flow_value = R.graph['flow_value']
78
        flow_dict = build_flow_dict(G, R)
79
        assert_equal(flow_value, solnValue, msg=msg.format(flow_func.__name__))
80
        validate_flows(G, s, t, flow_dict, solnValue, capacity, flow_func)
81
        # Minimum cut
82
        cut_value, partition = nx.minimum_cut(G, s, t, capacity=capacity,
83
                                              flow_func=flow_func)
84
        validate_cuts(G, s, t, solnValue, partition, capacity, flow_func)
85

    
86

    
87
class TestMaxflowMinCutCommon:
88

    
89
    def test_graph1(self):
90
        # Trivial undirected graph
91
        G = nx.Graph()
92
        G.add_edge(1, 2, capacity=1.0)
93

    
94
        solnFlows = {1: {2: 1.0},
95
                     2: {1: 1.0}}
96

    
97
        compare_flows_and_cuts(G, 1, 2, solnFlows, 1.0)
98

    
99
    def test_graph2(self):
100
        # A more complex undirected graph
101
        # adapted from www.topcoder.com/tc?module=Statc&d1=tutorials&d2=maxFlow
102
        G = nx.Graph()
103
        G.add_edge('x', 'a', capacity=3.0)
104
        G.add_edge('x', 'b', capacity=1.0)
105
        G.add_edge('a', 'c', capacity=3.0)
106
        G.add_edge('b', 'c', capacity=5.0)
107
        G.add_edge('b', 'd', capacity=4.0)
108
        G.add_edge('d', 'e', capacity=2.0)
109
        G.add_edge('c', 'y', capacity=2.0)
110
        G.add_edge('e', 'y', capacity=3.0)
111

    
112
        H = {'x': {'a': 3, 'b': 1},
113
             'a': {'c': 3, 'x': 3},
114
             'b': {'c': 1, 'd': 2, 'x': 1},
115
             'c': {'a': 3, 'b': 1, 'y': 2},
116
             'd': {'b': 2, 'e': 2},
117
             'e': {'d': 2, 'y': 2},
118
             'y': {'c': 2, 'e': 2}}
119

    
120
        compare_flows_and_cuts(G, 'x', 'y', H, 4.0)
121

    
122
    def test_digraph1(self):
123
        # The classic directed graph example
124
        G = nx.DiGraph()
125
        G.add_edge('a', 'b', capacity=1000.0)
126
        G.add_edge('a', 'c', capacity=1000.0)
127
        G.add_edge('b', 'c', capacity=1.0)
128
        G.add_edge('b', 'd', capacity=1000.0)
129
        G.add_edge('c', 'd', capacity=1000.0)
130

    
131
        H = {'a': {'b': 1000.0, 'c': 1000.0},
132
             'b': {'c': 0, 'd': 1000.0},
133
             'c': {'d': 1000.0},
134
             'd': {}}
135

    
136
        compare_flows_and_cuts(G, 'a', 'd', H, 2000.0)
137

    
138
    def test_digraph2(self):
139
        # An example in which some edges end up with zero flow.
140
        G = nx.DiGraph()
141
        G.add_edge('s', 'b', capacity=2)
142
        G.add_edge('s', 'c', capacity=1)
143
        G.add_edge('c', 'd', capacity=1)
144
        G.add_edge('d', 'a', capacity=1)
145
        G.add_edge('b', 'a', capacity=2)
146
        G.add_edge('a', 't', capacity=2)
147

    
148
        H = {'s': {'b': 2, 'c': 0},
149
             'c': {'d': 0},
150
             'd': {'a': 0},
151
             'b': {'a': 2},
152
             'a': {'t': 2},
153
             't': {}}
154

    
155
        compare_flows_and_cuts(G, 's', 't', H, 2)
156

    
157
    def test_digraph3(self):
158
        # A directed graph example from Cormen et al.
159
        G = nx.DiGraph()
160
        G.add_edge('s', 'v1', capacity=16.0)
161
        G.add_edge('s', 'v2', capacity=13.0)
162
        G.add_edge('v1', 'v2', capacity=10.0)
163
        G.add_edge('v2', 'v1', capacity=4.0)
164
        G.add_edge('v1', 'v3', capacity=12.0)
165
        G.add_edge('v3', 'v2', capacity=9.0)
166
        G.add_edge('v2', 'v4', capacity=14.0)
167
        G.add_edge('v4', 'v3', capacity=7.0)
168
        G.add_edge('v3', 't', capacity=20.0)
169
        G.add_edge('v4', 't', capacity=4.0)
170

    
171
        H = {'s': {'v1': 12.0, 'v2': 11.0},
172
             'v2': {'v1': 0, 'v4': 11.0},
173
             'v1': {'v2': 0, 'v3': 12.0},
174
             'v3': {'v2': 0, 't': 19.0},
175
             'v4': {'v3': 7.0, 't': 4.0},
176
             't': {}}
177

    
178
        compare_flows_and_cuts(G, 's', 't', H, 23.0)
179

    
180
    def test_digraph4(self):
181
        # A more complex directed graph
182
        # from www.topcoder.com/tc?module=Statc&d1=tutorials&d2=maxFlow
183
        G = nx.DiGraph()
184
        G.add_edge('x', 'a', capacity=3.0)
185
        G.add_edge('x', 'b', capacity=1.0)
186
        G.add_edge('a', 'c', capacity=3.0)
187
        G.add_edge('b', 'c', capacity=5.0)
188
        G.add_edge('b', 'd', capacity=4.0)
189
        G.add_edge('d', 'e', capacity=2.0)
190
        G.add_edge('c', 'y', capacity=2.0)
191
        G.add_edge('e', 'y', capacity=3.0)
192

    
193
        H = {'x': {'a': 2.0, 'b': 1.0},
194
             'a': {'c': 2.0},
195
             'b': {'c': 0, 'd': 1.0},
196
             'c': {'y': 2.0},
197
             'd': {'e': 1.0},
198
             'e': {'y': 1.0},
199
             'y': {}}
200

    
201
        compare_flows_and_cuts(G, 'x', 'y', H, 3.0)
202

    
203
    def test_wikipedia_dinitz_example(self):
204
        # Nice example from https://en.wikipedia.org/wiki/Dinic's_algorithm
205
        G = nx.DiGraph()
206
        G.add_edge('s', 1, capacity=10)
207
        G.add_edge('s', 2, capacity=10)
208
        G.add_edge(1, 3, capacity=4)
209
        G.add_edge(1, 4, capacity=8)
210
        G.add_edge(1, 2, capacity=2)
211
        G.add_edge(2, 4, capacity=9)
212
        G.add_edge(3, 't', capacity=10)
213
        G.add_edge(4, 3, capacity=6)
214
        G.add_edge(4, 't', capacity=10)
215

    
216
        solnFlows = {1: {2: 0, 3: 4, 4: 6},
217
                     2: {4: 9},
218
                     3: {'t': 9},
219
                     4: {3: 5, 't': 10},
220
                     's': {1: 10, 2: 9},
221
                     't': {}}
222

    
223
        compare_flows_and_cuts(G, 's', 't', solnFlows, 19)
224

    
225
    def test_optional_capacity(self):
226
        # Test optional capacity parameter.
227
        G = nx.DiGraph()
228
        G.add_edge('x', 'a', spam=3.0)
229
        G.add_edge('x', 'b', spam=1.0)
230
        G.add_edge('a', 'c', spam=3.0)
231
        G.add_edge('b', 'c', spam=5.0)
232
        G.add_edge('b', 'd', spam=4.0)
233
        G.add_edge('d', 'e', spam=2.0)
234
        G.add_edge('c', 'y', spam=2.0)
235
        G.add_edge('e', 'y', spam=3.0)
236

    
237
        solnFlows = {'x': {'a': 2.0, 'b': 1.0},
238
                     'a': {'c': 2.0},
239
                     'b': {'c': 0, 'd': 1.0},
240
                     'c': {'y': 2.0},
241
                     'd': {'e': 1.0},
242
                     'e': {'y': 1.0},
243
                     'y': {}}
244
        solnValue = 3.0
245
        s = 'x'
246
        t = 'y'
247

    
248
        compare_flows_and_cuts(G, s, t, solnFlows, solnValue, capacity='spam')
249

    
250
    def test_digraph_infcap_edges(self):
251
        # DiGraph with infinite capacity edges
252
        G = nx.DiGraph()
253
        G.add_edge('s', 'a')
254
        G.add_edge('s', 'b', capacity=30)
255
        G.add_edge('a', 'c', capacity=25)
256
        G.add_edge('b', 'c', capacity=12)
257
        G.add_edge('a', 't', capacity=60)
258
        G.add_edge('c', 't')
259

    
260
        H = {'s': {'a': 85, 'b': 12},
261
             'a': {'c': 25, 't': 60},
262
             'b': {'c': 12},
263
             'c': {'t': 37},
264
             't': {}}
265

    
266
        compare_flows_and_cuts(G, 's', 't', H, 97)
267

    
268
        # DiGraph with infinite capacity digon
269
        G = nx.DiGraph()
270
        G.add_edge('s', 'a', capacity=85)
271
        G.add_edge('s', 'b', capacity=30)
272
        G.add_edge('a', 'c')
273
        G.add_edge('c', 'a')
274
        G.add_edge('b', 'c', capacity=12)
275
        G.add_edge('a', 't', capacity=60)
276
        G.add_edge('c', 't', capacity=37)
277

    
278
        H = {'s': {'a': 85, 'b': 12},
279
             'a': {'c': 25, 't': 60},
280
             'c': {'a': 0, 't': 37},
281
             'b': {'c': 12},
282
             't': {}}
283

    
284
        compare_flows_and_cuts(G, 's', 't', H, 97)
285

    
286
    def test_digraph_infcap_path(self):
287
        # Graph with infinite capacity (s, t)-path
288
        G = nx.DiGraph()
289
        G.add_edge('s', 'a')
290
        G.add_edge('s', 'b', capacity=30)
291
        G.add_edge('a', 'c')
292
        G.add_edge('b', 'c', capacity=12)
293
        G.add_edge('a', 't', capacity=60)
294
        G.add_edge('c', 't')
295

    
296
        for flow_func in all_funcs:
297
            assert_raises(nx.NetworkXUnbounded,
298
                          flow_func, G, 's', 't')
299

    
300
    def test_graph_infcap_edges(self):
301
        # Undirected graph with infinite capacity edges
302
        G = nx.Graph()
303
        G.add_edge('s', 'a')
304
        G.add_edge('s', 'b', capacity=30)
305
        G.add_edge('a', 'c', capacity=25)
306
        G.add_edge('b', 'c', capacity=12)
307
        G.add_edge('a', 't', capacity=60)
308
        G.add_edge('c', 't')
309

    
310
        H = {'s': {'a': 85, 'b': 12},
311
             'a': {'c': 25, 's': 85, 't': 60},
312
             'b': {'c': 12, 's': 12},
313
             'c': {'a': 25, 'b': 12, 't': 37},
314
             't': {'a': 60, 'c': 37}}
315

    
316
        compare_flows_and_cuts(G, 's', 't', H, 97)
317

    
318
    def test_digraph5(self):
319
        # From ticket #429 by mfrasca.
320
        G = nx.DiGraph()
321
        G.add_edge('s', 'a', capacity=2)
322
        G.add_edge('s', 'b', capacity=2)
323
        G.add_edge('a', 'b', capacity=5)
324
        G.add_edge('a', 't', capacity=1)
325
        G.add_edge('b', 'a', capacity=1)
326
        G.add_edge('b', 't', capacity=3)
327
        flowSoln = {'a': {'b': 1, 't': 1},
328
                    'b': {'a': 0, 't': 3},
329
                    's': {'a': 2, 'b': 2},
330
                    't': {}}
331
        compare_flows_and_cuts(G, 's', 't', flowSoln, 4)
332

    
333
    def test_disconnected(self):
334
        G = nx.Graph()
335
        G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight='capacity')
336
        G.remove_node(1)
337
        assert_equal(nx.maximum_flow_value(G, 0, 3), 0)
338
        flowSoln = {0: {}, 2: {3: 0}, 3: {2: 0}}
339
        compare_flows_and_cuts(G, 0, 3, flowSoln, 0)
340

    
341
    def test_source_target_not_in_graph(self):
342
        G = nx.Graph()
343
        G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight='capacity')
344
        G.remove_node(0)
345
        for flow_func in all_funcs:
346
            assert_raises(nx.NetworkXError, flow_func, G, 0, 3)
347
        G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight='capacity')
348
        G.remove_node(3)
349
        for flow_func in all_funcs:
350
            assert_raises(nx.NetworkXError, flow_func, G, 0, 3)
351

    
352
    def test_source_target_coincide(self):
353
        G = nx.Graph()
354
        G.add_node(0)
355
        for flow_func in all_funcs:
356
            assert_raises(nx.NetworkXError, flow_func, G, 0, 0)
357

    
358
    def test_multigraphs_raise(self):
359
        G = nx.MultiGraph()
360
        M = nx.MultiDiGraph()
361
        G.add_edges_from([(0, 1), (1, 0)], capacity=True)
362
        for flow_func in all_funcs:
363
            assert_raises(nx.NetworkXError, flow_func, G, 0, 0)
364

    
365

    
366
class TestMaxFlowMinCutInterface:
367

    
368
    def setup(self):
369
        G = nx.DiGraph()
370
        G.add_edge('x', 'a', capacity=3.0)
371
        G.add_edge('x', 'b', capacity=1.0)
372
        G.add_edge('a', 'c', capacity=3.0)
373
        G.add_edge('b', 'c', capacity=5.0)
374
        G.add_edge('b', 'd', capacity=4.0)
375
        G.add_edge('d', 'e', capacity=2.0)
376
        G.add_edge('c', 'y', capacity=2.0)
377
        G.add_edge('e', 'y', capacity=3.0)
378
        self.G = G
379
        H = nx.DiGraph()
380
        H.add_edge(0, 1, capacity=1.0)
381
        H.add_edge(1, 2, capacity=1.0)
382
        self.H = H
383

    
384
    def test_flow_func_not_callable(self):
385
        elements = ['this_should_be_callable', 10, set([1, 2, 3])]
386
        G = nx.Graph()
387
        G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight='capacity')
388
        for flow_func in interface_funcs:
389
            for element in elements:
390
                assert_raises(nx.NetworkXError,
391
                              flow_func, G, 0, 1, flow_func=element)
392
                assert_raises(nx.NetworkXError,
393
                              flow_func, G, 0, 1, flow_func=element)
394

    
395
    def test_flow_func_parameters(self):
396
        G = self.G
397
        fv = 3.0
398
        for interface_func in interface_funcs:
399
            for flow_func in flow_funcs:
400
                result = interface_func(G, 'x', 'y', flow_func=flow_func)
401
                if interface_func in max_min_funcs:
402
                    result = result[0]
403
                assert_equal(fv, result, msg=msgi.format(flow_func.__name__,
404
                                                         interface_func.__name__))
405

    
406
    def test_minimum_cut_no_cutoff(self):
407
        G = self.G
408
        for flow_func in flow_funcs:
409
            assert_raises(nx.NetworkXError, nx.minimum_cut, G, 'x', 'y',
410
                          flow_func=flow_func, cutoff=1.0)
411
            assert_raises(nx.NetworkXError, nx.minimum_cut_value, G, 'x', 'y',
412
                          flow_func=flow_func, cutoff=1.0)
413

    
414
    def test_kwargs(self):
415
        G = self.H
416
        fv = 1.0
417
        to_test = (
418
            (shortest_augmenting_path, dict(two_phase=True)),
419
            (preflow_push, dict(global_relabel_freq=5)),
420
        )
421
        for interface_func in interface_funcs:
422
            for flow_func, kwargs in to_test:
423
                result = interface_func(G, 0, 2, flow_func=flow_func, **kwargs)
424
                if interface_func in max_min_funcs:
425
                    result = result[0]
426
                assert_equal(fv, result, msg=msgi.format(flow_func.__name__,
427
                                                         interface_func.__name__))
428

    
429
    def test_kwargs_default_flow_func(self):
430
        G = self.H
431
        for interface_func in interface_funcs:
432
            assert_raises(nx.NetworkXError, interface_func,
433
                          G, 0, 1, global_relabel_freq=2)
434

    
435
    def test_reusing_residual(self):
436
        G = self.G
437
        fv = 3.0
438
        s, t = 'x', 'y'
439
        R = build_residual_network(G, 'capacity')
440
        for interface_func in interface_funcs:
441
            for flow_func in flow_funcs:
442
                for i in range(3):
443
                    result = interface_func(G, 'x', 'y', flow_func=flow_func,
444
                                            residual=R)
445
                    if interface_func in max_min_funcs:
446
                        result = result[0]
447
                    assert_equal(fv, result,
448
                                 msg=msgi.format(flow_func.__name__,
449
                                                 interface_func.__name__))
450

    
451

    
452
# Tests specific to one algorithm
453
def test_preflow_push_global_relabel_freq():
454
    G = nx.DiGraph()
455
    G.add_edge(1, 2, capacity=1)
456
    R = preflow_push(G, 1, 2, global_relabel_freq=None)
457
    assert_equal(R.graph['flow_value'], 1)
458
    assert_raises(nx.NetworkXError, preflow_push, G, 1, 2,
459
                  global_relabel_freq=-1)
460

    
461

    
462
def test_preflow_push_makes_enough_space():
463
    # From ticket #1542
464
    G = nx.DiGraph()
465
    nx.add_path(G, [0, 1, 3], capacity=1)
466
    nx.add_path(G, [1, 2, 3], capacity=1)
467
    R = preflow_push(G, 0, 3, value_only=False)
468
    assert_equal(R.graph['flow_value'], 1)
469

    
470

    
471
def test_shortest_augmenting_path_two_phase():
472
    k = 5
473
    p = 1000
474
    G = nx.DiGraph()
475
    for i in range(k):
476
        G.add_edge('s', (i, 0), capacity=1)
477
        nx.add_path(G, ((i, j) for j in range(p)), capacity=1)
478
        G.add_edge((i, p - 1), 't', capacity=1)
479
    R = shortest_augmenting_path(G, 's', 't', two_phase=True)
480
    assert_equal(R.graph['flow_value'], k)
481
    R = shortest_augmenting_path(G, 's', 't', two_phase=False)
482
    assert_equal(R.graph['flow_value'], k)
483

    
484

    
485
class TestCutoff:
486

    
487
    def test_cutoff(self):
488
        k = 5
489
        p = 1000
490
        G = nx.DiGraph()
491
        for i in range(k):
492
            G.add_edge('s', (i, 0), capacity=2)
493
            nx.add_path(G, ((i, j) for j in range(p)), capacity=2)
494
            G.add_edge((i, p - 1), 't', capacity=2)
495
        R = shortest_augmenting_path(G, 's', 't', two_phase=True, cutoff=k)
496
        ok_(k <= R.graph['flow_value'] <= 2 * k)
497
        R = shortest_augmenting_path(G, 's', 't', two_phase=False, cutoff=k)
498
        ok_(k <= R.graph['flow_value'] <= 2 * k)
499
        R = edmonds_karp(G, 's', 't', cutoff=k)
500
        ok_(k <= R.graph['flow_value'] <= 2 * k)
501

    
502
    def test_complete_graph_cutoff(self):
503
        G = nx.complete_graph(5)
504
        nx.set_edge_attributes(G, {(u, v): 1 for u, v in G.edges()},
505
                               'capacity')
506
        for flow_func in [shortest_augmenting_path, edmonds_karp]:
507
            for cutoff in [3, 2, 1]:
508
                result = nx.maximum_flow_value(G, 0, 4, flow_func=flow_func,
509
                                               cutoff=cutoff)
510
                assert_equal(cutoff, result,
511
                             msg="cutoff error in {0}".format(flow_func.__name__))