Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (22.5 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Maximum flow (and minimum cut) algorithms on capacitated graphs.
4
"""
5
import networkx as nx
6

    
7
from .boykovkolmogorov import boykov_kolmogorov
8
from .dinitz_alg import dinitz
9
from .edmondskarp import edmonds_karp
10
from .preflowpush import preflow_push
11
from .shortestaugmentingpath import shortest_augmenting_path
12
from .utils import build_flow_dict
13
# Define the default flow function for computing maximum flow.
14
default_flow_func = preflow_push
15
# Functions that don't support cutoff for minimum cut computations.
16
flow_funcs = [
17
    boykov_kolmogorov,
18
    dinitz,
19
    edmonds_karp,
20
    preflow_push,
21
    shortest_augmenting_path,
22
]
23

    
24
__all__ = ['maximum_flow',
25
           'maximum_flow_value',
26
           'minimum_cut',
27
           'minimum_cut_value']
28

    
29

    
30
def maximum_flow(flowG, _s, _t,
31
                 capacity='capacity', flow_func=None, **kwargs):
32
    """Find a maximum single-commodity flow.
33

34
    Parameters
35
    ----------
36
    flowG : NetworkX graph
37
        Edges of the graph are expected to have an attribute called
38
        'capacity'. If this attribute is not present, the edge is
39
        considered to have infinite capacity.
40

41
    _s : node
42
        Source node for the flow.
43

44
    _t : node
45
        Sink node for the flow.
46

47
    capacity : string
48
        Edges of the graph G are expected to have an attribute capacity
49
        that indicates how much flow the edge can support. If this
50
        attribute is not present, the edge is considered to have
51
        infinite capacity. Default value: 'capacity'.
52

53
    flow_func : function
54
        A function for computing the maximum flow among a pair of nodes
55
        in a capacitated graph. The function has to accept at least three
56
        parameters: a Graph or Digraph, a source node, and a target node.
57
        And return a residual network that follows NetworkX conventions
58
        (see Notes). If flow_func is None, the default maximum
59
        flow function (:meth:`preflow_push`) is used. See below for
60
        alternative algorithms. The choice of the default function may change
61
        from version to version and should not be relied on. Default value:
62
        None.
63

64
    kwargs : Any other keyword parameter is passed to the function that
65
        computes the maximum flow.
66

67
    Returns
68
    -------
69
    flow_value : integer, float
70
        Value of the maximum flow, i.e., net outflow from the source.
71

72
    flow_dict : dict
73
        A dictionary containing the value of the flow that went through
74
        each edge.
75

76
    Raises
77
    ------
78
    NetworkXError
79
        The algorithm does not support MultiGraph and MultiDiGraph. If
80
        the input graph is an instance of one of these two classes, a
81
        NetworkXError is raised.
82

83
    NetworkXUnbounded
84
        If the graph has a path of infinite capacity, the value of a
85
        feasible flow on the graph is unbounded above and the function
86
        raises a NetworkXUnbounded.
87

88
    See also
89
    --------
90
    :meth:`maximum_flow_value`
91
    :meth:`minimum_cut`
92
    :meth:`minimum_cut_value`
93
    :meth:`edmonds_karp`
94
    :meth:`preflow_push`
95
    :meth:`shortest_augmenting_path`
96

97
    Notes
98
    -----
99
    The function used in the flow_func parameter has to return a residual
100
    network that follows NetworkX conventions:
101

102
    The residual network :samp:`R` from an input graph :samp:`G` has the
103
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
104
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
105
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
106
    in :samp:`G`.
107

108
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
109
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
110
    in :samp:`G` or zero otherwise. If the capacity is infinite,
111
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
112
    that does not affect the solution of the problem. This value is stored in
113
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
114
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
115
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
116

117
    The flow value, defined as the total flow into :samp:`t`, the sink, is
118
    stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using
119
    only edges :samp:`(u, v)` such that
120
    :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
121
    :samp:`s`-:samp:`t` cut.
122

123
    Specific algorithms may store extra data in :samp:`R`.
124

125
    The function should supports an optional boolean parameter value_only. When
126
    True, it can optionally terminate the algorithm as soon as the maximum flow
127
    value and the minimum cut can be determined.
128

129
    Examples
130
    --------
131
    >>> import networkx as nx
132
    >>> G = nx.DiGraph()
133
    >>> G.add_edge('x','a', capacity=3.0)
134
    >>> G.add_edge('x','b', capacity=1.0)
135
    >>> G.add_edge('a','c', capacity=3.0)
136
    >>> G.add_edge('b','c', capacity=5.0)
137
    >>> G.add_edge('b','d', capacity=4.0)
138
    >>> G.add_edge('d','e', capacity=2.0)
139
    >>> G.add_edge('c','y', capacity=2.0)
140
    >>> G.add_edge('e','y', capacity=3.0)
141

142
    maximum_flow returns both the value of the maximum flow and a
143
    dictionary with all flows.
144

145
    >>> flow_value, flow_dict = nx.maximum_flow(G, 'x', 'y')
146
    >>> flow_value
147
    3.0
148
    >>> print(flow_dict['x']['b'])
149
    1.0
150

151
    You can also use alternative algorithms for computing the
152
    maximum flow by using the flow_func parameter.
153

154
    >>> from networkx.algorithms.flow import shortest_augmenting_path
155
    >>> flow_value == nx.maximum_flow(G, 'x', 'y',
156
    ...                         flow_func=shortest_augmenting_path)[0]
157
    True
158

159
    """
160
    if flow_func is None:
161
        if kwargs:
162
            raise nx.NetworkXError("You have to explicitly set a flow_func if"
163
                                   " you need to pass parameters via kwargs.")
164
        flow_func = default_flow_func
165

    
166
    if not callable(flow_func):
167
        raise nx.NetworkXError("flow_func has to be callable.")
168

    
169
    R = flow_func(flowG, _s, _t, capacity=capacity, value_only=False, **kwargs)
170
    flow_dict = build_flow_dict(flowG, R)
171

    
172
    return (R.graph['flow_value'], flow_dict)
173

    
174

    
175
def maximum_flow_value(flowG, _s, _t,
176
                       capacity='capacity', flow_func=None, **kwargs):
177
    """Find the value of maximum single-commodity flow.
178

179
    Parameters
180
    ----------
181
    flowG : NetworkX graph
182
        Edges of the graph are expected to have an attribute called
183
        'capacity'. If this attribute is not present, the edge is
184
        considered to have infinite capacity.
185

186
    _s : node
187
        Source node for the flow.
188

189
    _t : node
190
        Sink node for the flow.
191

192
    capacity : string
193
        Edges of the graph G are expected to have an attribute capacity
194
        that indicates how much flow the edge can support. If this
195
        attribute is not present, the edge is considered to have
196
        infinite capacity. Default value: 'capacity'.
197

198
    flow_func : function
199
        A function for computing the maximum flow among a pair of nodes
200
        in a capacitated graph. The function has to accept at least three
201
        parameters: a Graph or Digraph, a source node, and a target node.
202
        And return a residual network that follows NetworkX conventions
203
        (see Notes). If flow_func is None, the default maximum
204
        flow function (:meth:`preflow_push`) is used. See below for
205
        alternative algorithms. The choice of the default function may change
206
        from version to version and should not be relied on. Default value:
207
        None.
208

209
    kwargs : Any other keyword parameter is passed to the function that
210
        computes the maximum flow.
211

212
    Returns
213
    -------
214
    flow_value : integer, float
215
        Value of the maximum flow, i.e., net outflow from the source.
216

217
    Raises
218
    ------
219
    NetworkXError
220
        The algorithm does not support MultiGraph and MultiDiGraph. If
221
        the input graph is an instance of one of these two classes, a
222
        NetworkXError is raised.
223

224
    NetworkXUnbounded
225
        If the graph has a path of infinite capacity, the value of a
226
        feasible flow on the graph is unbounded above and the function
227
        raises a NetworkXUnbounded.
228

229
    See also
230
    --------
231
    :meth:`maximum_flow`
232
    :meth:`minimum_cut`
233
    :meth:`minimum_cut_value`
234
    :meth:`edmonds_karp`
235
    :meth:`preflow_push`
236
    :meth:`shortest_augmenting_path`
237

238
    Notes
239
    -----
240
    The function used in the flow_func parameter has to return a residual
241
    network that follows NetworkX conventions:
242

243
    The residual network :samp:`R` from an input graph :samp:`G` has the
244
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
245
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
246
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
247
    in :samp:`G`.
248

249
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
250
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
251
    in :samp:`G` or zero otherwise. If the capacity is infinite,
252
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
253
    that does not affect the solution of the problem. This value is stored in
254
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
255
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
256
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
257

258
    The flow value, defined as the total flow into :samp:`t`, the sink, is
259
    stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using
260
    only edges :samp:`(u, v)` such that
261
    :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
262
    :samp:`s`-:samp:`t` cut.
263

264
    Specific algorithms may store extra data in :samp:`R`.
265

266
    The function should supports an optional boolean parameter value_only. When
267
    True, it can optionally terminate the algorithm as soon as the maximum flow
268
    value and the minimum cut can be determined.
269

270
    Examples
271
    --------
272
    >>> import networkx as nx
273
    >>> G = nx.DiGraph()
274
    >>> G.add_edge('x','a', capacity=3.0)
275
    >>> G.add_edge('x','b', capacity=1.0)
276
    >>> G.add_edge('a','c', capacity=3.0)
277
    >>> G.add_edge('b','c', capacity=5.0)
278
    >>> G.add_edge('b','d', capacity=4.0)
279
    >>> G.add_edge('d','e', capacity=2.0)
280
    >>> G.add_edge('c','y', capacity=2.0)
281
    >>> G.add_edge('e','y', capacity=3.0)
282

283
    maximum_flow_value computes only the value of the
284
    maximum flow:
285

286
    >>> flow_value = nx.maximum_flow_value(G, 'x', 'y')
287
    >>> flow_value
288
    3.0
289

290
    You can also use alternative algorithms for computing the
291
    maximum flow by using the flow_func parameter.
292

293
    >>> from networkx.algorithms.flow import shortest_augmenting_path
294
    >>> flow_value == nx.maximum_flow_value(G, 'x', 'y',
295
    ...                                     flow_func=shortest_augmenting_path)
296
    True
297

298
    """
299
    if flow_func is None:
300
        if kwargs:
301
            raise nx.NetworkXError("You have to explicitly set a flow_func if"
302
                                   " you need to pass parameters via kwargs.")
303
        flow_func = default_flow_func
304

    
305
    if not callable(flow_func):
306
        raise nx.NetworkXError("flow_func has to be callable.")
307

    
308
    R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
309

    
310
    return R.graph['flow_value']
311

    
312

    
313
def minimum_cut(flowG, _s, _t,
314
                capacity='capacity', flow_func=None, **kwargs):
315
    """Compute the value and the node partition of a minimum (s, t)-cut.
316

317
    Use the max-flow min-cut theorem, i.e., the capacity of a minimum
318
    capacity cut is equal to the flow value of a maximum flow.
319

320
    Parameters
321
    ----------
322
    flowG : NetworkX graph
323
        Edges of the graph are expected to have an attribute called
324
        'capacity'. If this attribute is not present, the edge is
325
        considered to have infinite capacity.
326

327
    _s : node
328
        Source node for the flow.
329

330
    _t : node
331
        Sink node for the flow.
332

333
    capacity : string
334
        Edges of the graph G are expected to have an attribute capacity
335
        that indicates how much flow the edge can support. If this
336
        attribute is not present, the edge is considered to have
337
        infinite capacity. Default value: 'capacity'.
338

339
    flow_func : function
340
        A function for computing the maximum flow among a pair of nodes
341
        in a capacitated graph. The function has to accept at least three
342
        parameters: a Graph or Digraph, a source node, and a target node.
343
        And return a residual network that follows NetworkX conventions
344
        (see Notes). If flow_func is None, the default maximum
345
        flow function (:meth:`preflow_push`) is used. See below for
346
        alternative algorithms. The choice of the default function may change
347
        from version to version and should not be relied on. Default value:
348
        None.
349

350
    kwargs : Any other keyword parameter is passed to the function that
351
        computes the maximum flow.
352

353
    Returns
354
    -------
355
    cut_value : integer, float
356
        Value of the minimum cut.
357

358
    partition : pair of node sets
359
        A partitioning of the nodes that defines a minimum cut.
360

361
    Raises
362
    ------
363
    NetworkXUnbounded
364
        If the graph has a path of infinite capacity, all cuts have
365
        infinite capacity and the function raises a NetworkXError.
366

367
    See also
368
    --------
369
    :meth:`maximum_flow`
370
    :meth:`maximum_flow_value`
371
    :meth:`minimum_cut_value`
372
    :meth:`edmonds_karp`
373
    :meth:`preflow_push`
374
    :meth:`shortest_augmenting_path`
375

376
    Notes
377
    -----
378
    The function used in the flow_func parameter has to return a residual
379
    network that follows NetworkX conventions:
380

381
    The residual network :samp:`R` from an input graph :samp:`G` has the
382
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
383
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
384
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
385
    in :samp:`G`.
386

387
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
388
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
389
    in :samp:`G` or zero otherwise. If the capacity is infinite,
390
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
391
    that does not affect the solution of the problem. This value is stored in
392
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
393
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
394
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
395

396
    The flow value, defined as the total flow into :samp:`t`, the sink, is
397
    stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using
398
    only edges :samp:`(u, v)` such that
399
    :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
400
    :samp:`s`-:samp:`t` cut.
401

402
    Specific algorithms may store extra data in :samp:`R`.
403

404
    The function should supports an optional boolean parameter value_only. When
405
    True, it can optionally terminate the algorithm as soon as the maximum flow
406
    value and the minimum cut can be determined.
407

408
    Examples
409
    --------
410
    >>> import networkx as nx
411
    >>> G = nx.DiGraph()
412
    >>> G.add_edge('x','a', capacity = 3.0)
413
    >>> G.add_edge('x','b', capacity = 1.0)
414
    >>> G.add_edge('a','c', capacity = 3.0)
415
    >>> G.add_edge('b','c', capacity = 5.0)
416
    >>> G.add_edge('b','d', capacity = 4.0)
417
    >>> G.add_edge('d','e', capacity = 2.0)
418
    >>> G.add_edge('c','y', capacity = 2.0)
419
    >>> G.add_edge('e','y', capacity = 3.0)
420

421
    minimum_cut computes both the value of the
422
    minimum cut and the node partition:
423

424
    >>> cut_value, partition = nx.minimum_cut(G, 'x', 'y')
425
    >>> reachable, non_reachable = partition
426

427
    'partition' here is a tuple with the two sets of nodes that define
428
    the minimum cut. You can compute the cut set of edges that induce
429
    the minimum cut as follows:
430

431
    >>> cutset = set()
432
    >>> for u, nbrs in ((n, G[n]) for n in reachable):
433
    ...     cutset.update((u, v) for v in nbrs if v in non_reachable)
434
    >>> print(sorted(cutset))
435
    [('c', 'y'), ('x', 'b')]
436
    >>> cut_value == sum(G.edges[u, v]['capacity'] for (u, v) in cutset)
437
    True
438

439
    You can also use alternative algorithms for computing the
440
    minimum cut by using the flow_func parameter.
441

442
    >>> from networkx.algorithms.flow import shortest_augmenting_path
443
    >>> cut_value == nx.minimum_cut(G, 'x', 'y',
444
    ...                             flow_func=shortest_augmenting_path)[0]
445
    True
446

447
    """
448
    if flow_func is None:
449
        if kwargs:
450
            raise nx.NetworkXError("You have to explicitly set a flow_func if"
451
                                   " you need to pass parameters via kwargs.")
452
        flow_func = default_flow_func
453

    
454
    if not callable(flow_func):
455
        raise nx.NetworkXError("flow_func has to be callable.")
456

    
457
    if kwargs.get('cutoff') is not None and flow_func in flow_funcs:
458
        raise nx.NetworkXError("cutoff should not be specified.")
459

    
460
    R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
461
    # Remove saturated edges from the residual network
462
    cutset = [(u, v, d) for u, v, d in R.edges(data=True)
463
              if d['flow'] == d['capacity']]
464
    R.remove_edges_from(cutset)
465

    
466
    # Then, reachable and non reachable nodes from source in the
467
    # residual network form the node partition that defines
468
    # the minimum cut.
469
    non_reachable = set(dict(nx.shortest_path_length(R, target=_t)))
470
    partition = (set(flowG) - non_reachable, non_reachable)
471
    # Finally add again cutset edges to the residual network to make
472
    # sure that it is reusable.
473
    if cutset is not None:
474
        R.add_edges_from(cutset)
475
    return (R.graph['flow_value'], partition)
476

    
477

    
478
def minimum_cut_value(flowG, _s, _t,
479
                      capacity='capacity', flow_func=None, **kwargs):
480
    """Compute the value of a minimum (s, t)-cut.
481

482
    Use the max-flow min-cut theorem, i.e., the capacity of a minimum
483
    capacity cut is equal to the flow value of a maximum flow.
484

485
    Parameters
486
    ----------
487
    flowG : NetworkX graph
488
        Edges of the graph are expected to have an attribute called
489
        'capacity'. If this attribute is not present, the edge is
490
        considered to have infinite capacity.
491

492
    _s : node
493
        Source node for the flow.
494

495
    _t : node
496
        Sink node for the flow.
497

498
    capacity : string
499
        Edges of the graph G are expected to have an attribute capacity
500
        that indicates how much flow the edge can support. If this
501
        attribute is not present, the edge is considered to have
502
        infinite capacity. Default value: 'capacity'.
503

504
    flow_func : function
505
        A function for computing the maximum flow among a pair of nodes
506
        in a capacitated graph. The function has to accept at least three
507
        parameters: a Graph or Digraph, a source node, and a target node.
508
        And return a residual network that follows NetworkX conventions
509
        (see Notes). If flow_func is None, the default maximum
510
        flow function (:meth:`preflow_push`) is used. See below for
511
        alternative algorithms. The choice of the default function may change
512
        from version to version and should not be relied on. Default value:
513
        None.
514

515
    kwargs : Any other keyword parameter is passed to the function that
516
        computes the maximum flow.
517

518
    Returns
519
    -------
520
    cut_value : integer, float
521
        Value of the minimum cut.
522

523
    Raises
524
    ------
525
    NetworkXUnbounded
526
        If the graph has a path of infinite capacity, all cuts have
527
        infinite capacity and the function raises a NetworkXError.
528

529
    See also
530
    --------
531
    :meth:`maximum_flow`
532
    :meth:`maximum_flow_value`
533
    :meth:`minimum_cut`
534
    :meth:`edmonds_karp`
535
    :meth:`preflow_push`
536
    :meth:`shortest_augmenting_path`
537

538
    Notes
539
    -----
540
    The function used in the flow_func parameter has to return a residual
541
    network that follows NetworkX conventions:
542

543
    The residual network :samp:`R` from an input graph :samp:`G` has the
544
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
545
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
546
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
547
    in :samp:`G`.
548

549
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
550
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
551
    in :samp:`G` or zero otherwise. If the capacity is infinite,
552
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
553
    that does not affect the solution of the problem. This value is stored in
554
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
555
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
556
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
557

558
    The flow value, defined as the total flow into :samp:`t`, the sink, is
559
    stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using
560
    only edges :samp:`(u, v)` such that
561
    :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
562
    :samp:`s`-:samp:`t` cut.
563

564
    Specific algorithms may store extra data in :samp:`R`.
565

566
    The function should supports an optional boolean parameter value_only. When
567
    True, it can optionally terminate the algorithm as soon as the maximum flow
568
    value and the minimum cut can be determined.
569

570
    Examples
571
    --------
572
    >>> import networkx as nx
573
    >>> G = nx.DiGraph()
574
    >>> G.add_edge('x','a', capacity = 3.0)
575
    >>> G.add_edge('x','b', capacity = 1.0)
576
    >>> G.add_edge('a','c', capacity = 3.0)
577
    >>> G.add_edge('b','c', capacity = 5.0)
578
    >>> G.add_edge('b','d', capacity = 4.0)
579
    >>> G.add_edge('d','e', capacity = 2.0)
580
    >>> G.add_edge('c','y', capacity = 2.0)
581
    >>> G.add_edge('e','y', capacity = 3.0)
582

583
    minimum_cut_value computes only the value of the
584
    minimum cut:
585

586
    >>> cut_value = nx.minimum_cut_value(G, 'x', 'y')
587
    >>> cut_value
588
    3.0
589

590
    You can also use alternative algorithms for computing the
591
    minimum cut by using the flow_func parameter.
592

593
    >>> from networkx.algorithms.flow import shortest_augmenting_path
594
    >>> cut_value == nx.minimum_cut_value(G, 'x', 'y',
595
    ...                                   flow_func=shortest_augmenting_path)
596
    True
597

598
    """
599
    if flow_func is None:
600
        if kwargs:
601
            raise nx.NetworkXError("You have to explicitly set a flow_func if"
602
                                   " you need to pass parameters via kwargs.")
603
        flow_func = default_flow_func
604

    
605
    if not callable(flow_func):
606
        raise nx.NetworkXError("flow_func has to be callable.")
607

    
608
    if kwargs.get('cutoff') is not None and flow_func in flow_funcs:
609
        raise nx.NetworkXError("cutoff should not be specified.")
610

    
611
    R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
612

    
613
    return R.graph['flow_value']