Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (29.6 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Flow based connectivity algorithms
4
"""
5
from __future__ import division
6

    
7
import itertools
8
from operator import itemgetter
9

    
10
import networkx as nx
11
# Define the default maximum flow function to use in all flow based
12
# connectivity algorithms.
13
from networkx.algorithms.flow import boykov_kolmogorov
14
from networkx.algorithms.flow import dinitz
15
from networkx.algorithms.flow import edmonds_karp
16
from networkx.algorithms.flow import shortest_augmenting_path
17
from networkx.algorithms.flow import build_residual_network
18
default_flow_func = edmonds_karp
19

    
20
from .utils import (build_auxiliary_node_connectivity,
21
                    build_auxiliary_edge_connectivity)
22

    
23
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>'])
24

    
25
__all__ = ['average_node_connectivity',
26
           'local_node_connectivity',
27
           'node_connectivity',
28
           'local_edge_connectivity',
29
           'edge_connectivity',
30
           'all_pairs_node_connectivity']
31

    
32

    
33
def local_node_connectivity(G, s, t, flow_func=None, auxiliary=None,
34
                            residual=None, cutoff=None):
35
    r"""Computes local node connectivity for nodes s and t.
36

37
    Local node connectivity for two non adjacent nodes s and t is the
38
    minimum number of nodes that must be removed (along with their incident
39
    edges) to disconnect them.
40

41
    This is a flow based implementation of node connectivity. We compute the
42
    maximum flow on an auxiliary digraph build from the original input
43
    graph (see below for details).
44

45
    Parameters
46
    ----------
47
    G : NetworkX graph
48
        Undirected graph
49

50
    s : node
51
        Source node
52

53
    t : node
54
        Target node
55

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

66
    auxiliary : NetworkX DiGraph
67
        Auxiliary digraph to compute flow based node connectivity. It has
68
        to have a graph attribute called mapping with a dictionary mapping
69
        node names in G and in the auxiliary digraph. If provided
70
        it will be reused instead of recreated. Default value: None.
71

72
    residual : NetworkX DiGraph
73
        Residual network to compute maximum flow. If provided it will be
74
        reused instead of recreated. Default value: None.
75

76
    cutoff : integer, float
77
        If specified, the maximum flow algorithm will terminate when the
78
        flow value reaches or exceeds the cutoff. This is only for the
79
        algorithms that support the cutoff parameter: :meth:`edmonds_karp`
80
        and :meth:`shortest_augmenting_path`. Other algorithms will ignore
81
        this parameter. Default value: None.
82

83
    Returns
84
    -------
85
    K : integer
86
        local node connectivity for nodes s and t
87

88
    Examples
89
    --------
90
    This function is not imported in the base NetworkX namespace, so you
91
    have to explicitly import it from the connectivity package:
92

93
    >>> from networkx.algorithms.connectivity import local_node_connectivity
94

95
    We use in this example the platonic icosahedral graph, which has node
96
    connectivity 5.
97

98
    >>> G = nx.icosahedral_graph()
99
    >>> local_node_connectivity(G, 0, 6)
100
    5
101

102
    If you need to compute local connectivity on several pairs of
103
    nodes in the same graph, it is recommended that you reuse the
104
    data structures that NetworkX uses in the computation: the
105
    auxiliary digraph for node connectivity, and the residual
106
    network for the underlying maximum flow computation.
107

108
    Example of how to compute local node connectivity among
109
    all pairs of nodes of the platonic icosahedral graph reusing
110
    the data structures.
111

112
    >>> import itertools
113
    >>> # You also have to explicitly import the function for
114
    >>> # building the auxiliary digraph from the connectivity package
115
    >>> from networkx.algorithms.connectivity import (
116
    ...     build_auxiliary_node_connectivity)
117
    ...
118
    >>> H = build_auxiliary_node_connectivity(G)
119
    >>> # And the function for building the residual network from the
120
    >>> # flow package
121
    >>> from networkx.algorithms.flow import build_residual_network
122
    >>> # Note that the auxiliary digraph has an edge attribute named capacity
123
    >>> R = build_residual_network(H, 'capacity')
124
    >>> result = dict.fromkeys(G, dict())
125
    >>> # Reuse the auxiliary digraph and the residual network by passing them
126
    >>> # as parameters
127
    >>> for u, v in itertools.combinations(G, 2):
128
    ...     k = local_node_connectivity(G, u, v, auxiliary=H, residual=R)
129
    ...     result[u][v] = k
130
    ...
131
    >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
132
    True
133

134
    You can also use alternative flow algorithms for computing node
135
    connectivity. For instance, in dense networks the algorithm
136
    :meth:`shortest_augmenting_path` will usually perform better than
137
    the default :meth:`edmonds_karp` which is faster for sparse
138
    networks with highly skewed degree distributions. Alternative flow
139
    functions have to be explicitly imported from the flow package.
140

141
    >>> from networkx.algorithms.flow import shortest_augmenting_path
142
    >>> local_node_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
143
    5
144

145
    Notes
146
    -----
147
    This is a flow based implementation of node connectivity. We compute the
148
    maximum flow using, by default, the :meth:`edmonds_karp` algorithm (see:
149
    :meth:`maximum_flow`) on an auxiliary digraph build from the original
150
    input graph:
151

152
    For an undirected graph G having `n` nodes and `m` edges we derive a
153
    directed graph H with `2n` nodes and `2m+n` arcs by replacing each
154
    original node `v` with two nodes `v_A`, `v_B` linked by an (internal)
155
    arc in H. Then for each edge (`u`, `v`) in G we add two arcs
156
    (`u_B`, `v_A`) and (`v_B`, `u_A`) in H. Finally we set the attribute
157
    capacity = 1 for each arc in H [1]_ .
158

159
    For a directed graph G having `n` nodes and `m` arcs we derive a
160
    directed graph H with `2n` nodes and `m+n` arcs by replacing each
161
    original node `v` with two nodes `v_A`, `v_B` linked by an (internal)
162
    arc (`v_A`, `v_B`) in H. Then for each arc (`u`, `v`) in G we add one arc
163
    (`u_B`, `v_A`) in H. Finally we set the attribute capacity = 1 for
164
    each arc in H.
165

166
    This is equal to the local node connectivity because the value of
167
    a maximum s-t-flow is equal to the capacity of a minimum s-t-cut.
168

169
    See also
170
    --------
171
    :meth:`local_edge_connectivity`
172
    :meth:`node_connectivity`
173
    :meth:`minimum_node_cut`
174
    :meth:`maximum_flow`
175
    :meth:`edmonds_karp`
176
    :meth:`preflow_push`
177
    :meth:`shortest_augmenting_path`
178

179
    References
180
    ----------
181
    .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and
182
        Erlebach, 'Network Analysis: Methodological Foundations', Lecture
183
        Notes in Computer Science, Volume 3418, Springer-Verlag, 2005.
184
        http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
185

186
    """
187
    if flow_func is None:
188
        flow_func = default_flow_func
189

    
190
    if auxiliary is None:
191
        H = build_auxiliary_node_connectivity(G)
192
    else:
193
        H = auxiliary
194

    
195
    mapping = H.graph.get('mapping', None)
196
    if mapping is None:
197
        raise nx.NetworkXError('Invalid auxiliary digraph.')
198

    
199
    kwargs = dict(flow_func=flow_func, residual=residual)
200
    if flow_func is shortest_augmenting_path:
201
        kwargs['cutoff'] = cutoff
202
        kwargs['two_phase'] = True
203
    elif flow_func is edmonds_karp:
204
        kwargs['cutoff'] = cutoff
205
    elif flow_func is dinitz:
206
        kwargs['cutoff'] = cutoff
207
    elif flow_func is boykov_kolmogorov:
208
        kwargs['cutoff'] = cutoff
209

    
210
    return nx.maximum_flow_value(H, '%sB' % mapping[s], '%sA' % mapping[t], **kwargs)
211

    
212

    
213
def node_connectivity(G, s=None, t=None, flow_func=None):
214
    r"""Returns node connectivity for a graph or digraph G.
215

216
    Node connectivity is equal to the minimum number of nodes that
217
    must be removed to disconnect G or render it trivial. If source
218
    and target nodes are provided, this function returns the local node
219
    connectivity: the minimum number of nodes that must be removed to break
220
    all paths from source to target in G.
221

222
    Parameters
223
    ----------
224
    G : NetworkX graph
225
        Undirected graph
226

227
    s : node
228
        Source node. Optional. Default value: None.
229

230
    t : node
231
        Target node. Optional. Default value: None.
232

233
    flow_func : function
234
        A function for computing the maximum flow among a pair of nodes.
235
        The function has to accept at least three parameters: a Digraph,
236
        a source node, and a target node. And return a residual network
237
        that follows NetworkX conventions (see :meth:`maximum_flow` for
238
        details). If flow_func is None, the default maximum flow function
239
        (:meth:`edmonds_karp`) is used. See below for details. The
240
        choice of the default function may change from version
241
        to version and should not be relied on. Default value: None.
242

243
    Returns
244
    -------
245
    K : integer
246
        Node connectivity of G, or local node connectivity if source
247
        and target are provided.
248

249
    Examples
250
    --------
251
    >>> # Platonic icosahedral graph is 5-node-connected
252
    >>> G = nx.icosahedral_graph()
253
    >>> nx.node_connectivity(G)
254
    5
255

256
    You can use alternative flow algorithms for the underlying maximum
257
    flow computation. In dense networks the algorithm
258
    :meth:`shortest_augmenting_path` will usually perform better
259
    than the default :meth:`edmonds_karp`, which is faster for
260
    sparse networks with highly skewed degree distributions. Alternative
261
    flow functions have to be explicitly imported from the flow package.
262

263
    >>> from networkx.algorithms.flow import shortest_augmenting_path
264
    >>> nx.node_connectivity(G, flow_func=shortest_augmenting_path)
265
    5
266

267
    If you specify a pair of nodes (source and target) as parameters,
268
    this function returns the value of local node connectivity.
269

270
    >>> nx.node_connectivity(G, 3, 7)
271
    5
272

273
    If you need to perform several local computations among different
274
    pairs of nodes on the same graph, it is recommended that you reuse
275
    the data structures used in the maximum flow computations. See
276
    :meth:`local_node_connectivity` for details.
277

278
    Notes
279
    -----
280
    This is a flow based implementation of node connectivity. The
281
    algorithm works by solving $O((n-\delta-1+\delta(\delta-1)/2))$
282
    maximum flow problems on an auxiliary digraph. Where $\delta$
283
    is the minimum degree of G. For details about the auxiliary
284
    digraph and the computation of local node connectivity see
285
    :meth:`local_node_connectivity`. This implementation is based
286
    on algorithm 11 in [1]_.
287

288
    See also
289
    --------
290
    :meth:`local_node_connectivity`
291
    :meth:`edge_connectivity`
292
    :meth:`maximum_flow`
293
    :meth:`edmonds_karp`
294
    :meth:`preflow_push`
295
    :meth:`shortest_augmenting_path`
296

297
    References
298
    ----------
299
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
300
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
301

302
    """
303
    if (s is not None and t is None) or (s is None and t is not None):
304
        raise nx.NetworkXError('Both source and target must be specified.')
305

    
306
    # Local node connectivity
307
    if s is not None and t is not None:
308
        if s not in G:
309
            raise nx.NetworkXError('node %s not in graph' % s)
310
        if t not in G:
311
            raise nx.NetworkXError('node %s not in graph' % t)
312
        return local_node_connectivity(G, s, t, flow_func=flow_func)
313

    
314
    # Global node connectivity
315
    if G.is_directed():
316
        if not nx.is_weakly_connected(G):
317
            return 0
318
        iter_func = itertools.permutations
319
        # It is necessary to consider both predecessors
320
        # and successors for directed graphs
321

    
322
        def neighbors(v):
323
            return itertools.chain.from_iterable([G.predecessors(v),
324
                                                  G.successors(v)])
325
    else:
326
        if not nx.is_connected(G):
327
            return 0
328
        iter_func = itertools.combinations
329
        neighbors = G.neighbors
330

    
331
    # Reuse the auxiliary digraph and the residual network
332
    H = build_auxiliary_node_connectivity(G)
333
    R = build_residual_network(H, 'capacity')
334
    kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R)
335

    
336
    # Pick a node with minimum degree
337
    # Node connectivity is bounded by degree.
338
    v, K = min(G.degree(), key=itemgetter(1))
339
    # compute local node connectivity with all its non-neighbors nodes
340
    for w in set(G) - set(neighbors(v)) - set([v]):
341
        kwargs['cutoff'] = K
342
        K = min(K, local_node_connectivity(G, v, w, **kwargs))
343
    # Also for non adjacent pairs of neighbors of v
344
    for x, y in iter_func(neighbors(v), 2):
345
        if y in G[x]:
346
            continue
347
        kwargs['cutoff'] = K
348
        K = min(K, local_node_connectivity(G, x, y, **kwargs))
349

    
350
    return K
351

    
352

    
353
def average_node_connectivity(G, flow_func=None):
354
    r"""Returns the average connectivity of a graph G.
355

356
    The average connectivity `\bar{\kappa}` of a graph G is the average
357
    of local node connectivity over all pairs of nodes of G [1]_ .
358

359
    .. math::
360

361
        \bar{\kappa}(G) = \frac{\sum_{u,v} \kappa_{G}(u,v)}{{n \choose 2}}
362

363
    Parameters
364
    ----------
365

366
    G : NetworkX graph
367
        Undirected graph
368

369
    flow_func : function
370
        A function for computing the maximum flow among a pair of nodes.
371
        The function has to accept at least three parameters: a Digraph,
372
        a source node, and a target node. And return a residual network
373
        that follows NetworkX conventions (see :meth:`maximum_flow` for
374
        details). If flow_func is None, the default maximum flow function
375
        (:meth:`edmonds_karp`) is used. See :meth:`local_node_connectivity`
376
        for details. The choice of the default function may change from
377
        version to version and should not be relied on. Default value: None.
378

379
    Returns
380
    -------
381
    K : float
382
        Average node connectivity
383

384
    See also
385
    --------
386
    :meth:`local_node_connectivity`
387
    :meth:`node_connectivity`
388
    :meth:`edge_connectivity`
389
    :meth:`maximum_flow`
390
    :meth:`edmonds_karp`
391
    :meth:`preflow_push`
392
    :meth:`shortest_augmenting_path`
393

394
    References
395
    ----------
396
    .. [1]  Beineke, L., O. Oellermann, and R. Pippert (2002). The average
397
            connectivity of a graph. Discrete mathematics 252(1-3), 31-45.
398
            http://www.sciencedirect.com/science/article/pii/S0012365X01001807
399

400
    """
401
    if G.is_directed():
402
        iter_func = itertools.permutations
403
    else:
404
        iter_func = itertools.combinations
405

    
406
    # Reuse the auxiliary digraph and the residual network
407
    H = build_auxiliary_node_connectivity(G)
408
    R = build_residual_network(H, 'capacity')
409
    kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R)
410

    
411
    num, den = 0, 0
412
    for u, v in iter_func(G, 2):
413
        num += local_node_connectivity(G, u, v, **kwargs)
414
        den += 1
415

    
416
    if den == 0:  # Null Graph
417
        return 0
418
    return num / den
419

    
420

    
421
def all_pairs_node_connectivity(G, nbunch=None, flow_func=None):
422
    """Compute node connectivity between all pairs of nodes of G.
423

424
    Parameters
425
    ----------
426
    G : NetworkX graph
427
        Undirected graph
428

429
    nbunch: container
430
        Container of nodes. If provided node connectivity will be computed
431
        only over pairs of nodes in nbunch.
432

433
    flow_func : function
434
        A function for computing the maximum flow among a pair of nodes.
435
        The function has to accept at least three parameters: a Digraph,
436
        a source node, and a target node. And return a residual network
437
        that follows NetworkX conventions (see :meth:`maximum_flow` for
438
        details). If flow_func is None, the default maximum flow function
439
        (:meth:`edmonds_karp`) is used. See below for details. The
440
        choice of the default function may change from version
441
        to version and should not be relied on. Default value: None.
442

443
    Returns
444
    -------
445
    all_pairs : dict
446
        A dictionary with node connectivity between all pairs of nodes
447
        in G, or in nbunch if provided.
448

449
    See also
450
    --------
451
    :meth:`local_node_connectivity`
452
    :meth:`edge_connectivity`
453
    :meth:`local_edge_connectivity`
454
    :meth:`maximum_flow`
455
    :meth:`edmonds_karp`
456
    :meth:`preflow_push`
457
    :meth:`shortest_augmenting_path`
458

459
    """
460
    if nbunch is None:
461
        nbunch = G
462
    else:
463
        nbunch = set(nbunch)
464

    
465
    directed = G.is_directed()
466
    if directed:
467
        iter_func = itertools.permutations
468
    else:
469
        iter_func = itertools.combinations
470

    
471
    all_pairs = {n: {} for n in nbunch}
472

    
473
    # Reuse auxiliary digraph and residual network
474
    H = build_auxiliary_node_connectivity(G)
475
    mapping = H.graph['mapping']
476
    R = build_residual_network(H, 'capacity')
477
    kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R)
478

    
479
    for u, v in iter_func(nbunch, 2):
480
        K = local_node_connectivity(G, u, v, **kwargs)
481
        all_pairs[u][v] = K
482
        if not directed:
483
            all_pairs[v][u] = K
484

    
485
    return all_pairs
486

    
487

    
488
def local_edge_connectivity(G, s, t, flow_func=None, auxiliary=None,
489
                            residual=None, cutoff=None):
490
    r"""Returns local edge connectivity for nodes s and t in G.
491

492
    Local edge connectivity for two nodes s and t is the minimum number
493
    of edges that must be removed to disconnect them.
494

495
    This is a flow based implementation of edge connectivity. We compute the
496
    maximum flow on an auxiliary digraph build from the original
497
    network (see below for details). This is equal to the local edge
498
    connectivity because the value of a maximum s-t-flow is equal to the
499
    capacity of a minimum s-t-cut (Ford and Fulkerson theorem) [1]_ .
500

501
    Parameters
502
    ----------
503
    G : NetworkX graph
504
        Undirected or directed graph
505

506
    s : node
507
        Source node
508

509
    t : node
510
        Target node
511

512
    flow_func : function
513
        A function for computing the maximum flow among a pair of nodes.
514
        The function has to accept at least three parameters: a Digraph,
515
        a source node, and a target node. And return a residual network
516
        that follows NetworkX conventions (see :meth:`maximum_flow` for
517
        details). If flow_func is None, the default maximum flow function
518
        (:meth:`edmonds_karp`) is used. See below for details. The
519
        choice of the default function may change from version
520
        to version and should not be relied on. Default value: None.
521

522
    auxiliary : NetworkX DiGraph
523
        Auxiliary digraph for computing flow based edge connectivity. If
524
        provided it will be reused instead of recreated. Default value: None.
525

526
    residual : NetworkX DiGraph
527
        Residual network to compute maximum flow. If provided it will be
528
        reused instead of recreated. Default value: None.
529

530
    cutoff : integer, float
531
        If specified, the maximum flow algorithm will terminate when the
532
        flow value reaches or exceeds the cutoff. This is only for the
533
        algorithms that support the cutoff parameter: :meth:`edmonds_karp`
534
        and :meth:`shortest_augmenting_path`. Other algorithms will ignore
535
        this parameter. Default value: None.
536

537
    Returns
538
    -------
539
    K : integer
540
        local edge connectivity for nodes s and t.
541

542
    Examples
543
    --------
544
    This function is not imported in the base NetworkX namespace, so you
545
    have to explicitly import it from the connectivity package:
546

547
    >>> from networkx.algorithms.connectivity import local_edge_connectivity
548

549
    We use in this example the platonic icosahedral graph, which has edge
550
    connectivity 5.
551

552
    >>> G = nx.icosahedral_graph()
553
    >>> local_edge_connectivity(G, 0, 6)
554
    5
555

556
    If you need to compute local connectivity on several pairs of
557
    nodes in the same graph, it is recommended that you reuse the
558
    data structures that NetworkX uses in the computation: the
559
    auxiliary digraph for edge connectivity, and the residual
560
    network for the underlying maximum flow computation.
561

562
    Example of how to compute local edge connectivity among
563
    all pairs of nodes of the platonic icosahedral graph reusing
564
    the data structures.
565

566
    >>> import itertools
567
    >>> # You also have to explicitly import the function for
568
    >>> # building the auxiliary digraph from the connectivity package
569
    >>> from networkx.algorithms.connectivity import (
570
    ...     build_auxiliary_edge_connectivity)
571
    >>> H = build_auxiliary_edge_connectivity(G)
572
    >>> # And the function for building the residual network from the
573
    >>> # flow package
574
    >>> from networkx.algorithms.flow import build_residual_network
575
    >>> # Note that the auxiliary digraph has an edge attribute named capacity
576
    >>> R = build_residual_network(H, 'capacity')
577
    >>> result = dict.fromkeys(G, dict())
578
    >>> # Reuse the auxiliary digraph and the residual network by passing them
579
    >>> # as parameters
580
    >>> for u, v in itertools.combinations(G, 2):
581
    ...     k = local_edge_connectivity(G, u, v, auxiliary=H, residual=R)
582
    ...     result[u][v] = k
583
    >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
584
    True
585

586
    You can also use alternative flow algorithms for computing edge
587
    connectivity. For instance, in dense networks the algorithm
588
    :meth:`shortest_augmenting_path` will usually perform better than
589
    the default :meth:`edmonds_karp` which is faster for sparse
590
    networks with highly skewed degree distributions. Alternative flow
591
    functions have to be explicitly imported from the flow package.
592

593
    >>> from networkx.algorithms.flow import shortest_augmenting_path
594
    >>> local_edge_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
595
    5
596

597
    Notes
598
    -----
599
    This is a flow based implementation of edge connectivity. We compute the
600
    maximum flow using, by default, the :meth:`edmonds_karp` algorithm on an
601
    auxiliary digraph build from the original input graph:
602

603
    If the input graph is undirected, we replace each edge (`u`,`v`) with
604
    two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute
605
    'capacity' for each arc to 1. If the input graph is directed we simply
606
    add the 'capacity' attribute. This is an implementation of algorithm 1
607
    in [1]_.
608

609
    The maximum flow in the auxiliary network is equal to the local edge
610
    connectivity because the value of a maximum s-t-flow is equal to the
611
    capacity of a minimum s-t-cut (Ford and Fulkerson theorem).
612

613
    See also
614
    --------
615
    :meth:`edge_connectivity`
616
    :meth:`local_node_connectivity`
617
    :meth:`node_connectivity`
618
    :meth:`maximum_flow`
619
    :meth:`edmonds_karp`
620
    :meth:`preflow_push`
621
    :meth:`shortest_augmenting_path`
622

623
    References
624
    ----------
625
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
626
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
627

628
    """
629
    if flow_func is None:
630
        flow_func = default_flow_func
631

    
632
    if auxiliary is None:
633
        H = build_auxiliary_edge_connectivity(G)
634
    else:
635
        H = auxiliary
636

    
637
    kwargs = dict(flow_func=flow_func, residual=residual)
638
    if flow_func is shortest_augmenting_path:
639
        kwargs['cutoff'] = cutoff
640
        kwargs['two_phase'] = True
641
    elif flow_func is edmonds_karp:
642
        kwargs['cutoff'] = cutoff
643
    elif flow_func is dinitz:
644
        kwargs['cutoff'] = cutoff
645
    elif flow_func is boykov_kolmogorov:
646
        kwargs['cutoff'] = cutoff
647

    
648
    return nx.maximum_flow_value(H, s, t, **kwargs)
649

    
650

    
651
def edge_connectivity(G, s=None, t=None, flow_func=None, cutoff=None):
652
    r"""Returns the edge connectivity of the graph or digraph G.
653

654
    The edge connectivity is equal to the minimum number of edges that
655
    must be removed to disconnect G or render it trivial. If source
656
    and target nodes are provided, this function returns the local edge
657
    connectivity: the minimum number of edges that must be removed to
658
    break all paths from source to target in G.
659

660
    Parameters
661
    ----------
662
    G : NetworkX graph
663
        Undirected or directed graph
664

665
    s : node
666
        Source node. Optional. Default value: None.
667

668
    t : node
669
        Target node. Optional. Default value: None.
670

671
    flow_func : function
672
        A function for computing the maximum flow among a pair of nodes.
673
        The function has to accept at least three parameters: a Digraph,
674
        a source node, and a target node. And return a residual network
675
        that follows NetworkX conventions (see :meth:`maximum_flow` for
676
        details). If flow_func is None, the default maximum flow function
677
        (:meth:`edmonds_karp`) is used. See below for details. The
678
        choice of the default function may change from version
679
        to version and should not be relied on. Default value: None.
680

681
    cutoff : integer, float
682
        If specified, the maximum flow algorithm will terminate when the
683
        flow value reaches or exceeds the cutoff. This is only for the
684
        algorithms that support the cutoff parameter: :meth:`edmonds_karp`
685
        and :meth:`shortest_augmenting_path`. Other algorithms will ignore
686
        this parameter. Default value: None.
687

688
    Returns
689
    -------
690
    K : integer
691
        Edge connectivity for G, or local edge connectivity if source
692
        and target were provided
693

694
    Examples
695
    --------
696
    >>> # Platonic icosahedral graph is 5-edge-connected
697
    >>> G = nx.icosahedral_graph()
698
    >>> nx.edge_connectivity(G)
699
    5
700

701
    You can use alternative flow algorithms for the underlying
702
    maximum flow computation. In dense networks the algorithm
703
    :meth:`shortest_augmenting_path` will usually perform better
704
    than the default :meth:`edmonds_karp`, which is faster for
705
    sparse networks with highly skewed degree distributions.
706
    Alternative flow functions have to be explicitly imported
707
    from the flow package.
708

709
    >>> from networkx.algorithms.flow import shortest_augmenting_path
710
    >>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
711
    5
712

713
    If you specify a pair of nodes (source and target) as parameters,
714
    this function returns the value of local edge connectivity.
715

716
    >>> nx.edge_connectivity(G, 3, 7)
717
    5
718

719
    If you need to perform several local computations among different
720
    pairs of nodes on the same graph, it is recommended that you reuse
721
    the data structures used in the maximum flow computations. See
722
    :meth:`local_edge_connectivity` for details.
723

724
    Notes
725
    -----
726
    This is a flow based implementation of global edge connectivity.
727
    For undirected graphs the algorithm works by finding a 'small'
728
    dominating set of nodes of G (see algorithm 7 in [1]_ ) and
729
    computing local maximum flow (see :meth:`local_edge_connectivity`)
730
    between an arbitrary node in the dominating set and the rest of
731
    nodes in it. This is an implementation of algorithm 6 in [1]_ .
732
    For directed graphs, the algorithm does n calls to the maximum
733
    flow function. This is an implementation of algorithm 8 in [1]_ .
734

735
    See also
736
    --------
737
    :meth:`local_edge_connectivity`
738
    :meth:`local_node_connectivity`
739
    :meth:`node_connectivity`
740
    :meth:`maximum_flow`
741
    :meth:`edmonds_karp`
742
    :meth:`preflow_push`
743
    :meth:`shortest_augmenting_path`
744
    :meth:`k_edge_components`
745
    :meth:`k_edge_subgraphs`
746

747
    References
748
    ----------
749
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
750
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
751

752
    """
753
    if (s is not None and t is None) or (s is None and t is not None):
754
        raise nx.NetworkXError('Both source and target must be specified.')
755

    
756
    # Local edge connectivity
757
    if s is not None and t is not None:
758
        if s not in G:
759
            raise nx.NetworkXError('node %s not in graph' % s)
760
        if t not in G:
761
            raise nx.NetworkXError('node %s not in graph' % t)
762
        return local_edge_connectivity(G, s, t, flow_func=flow_func,
763
                                       cutoff=cutoff)
764

    
765
    # Global edge connectivity
766
    # reuse auxiliary digraph and residual network
767
    H = build_auxiliary_edge_connectivity(G)
768
    R = build_residual_network(H, 'capacity')
769
    kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R)
770

    
771
    if G.is_directed():
772
        # Algorithm 8 in [1]
773
        if not nx.is_weakly_connected(G):
774
            return 0
775

    
776
        # initial value for \lambda is minimum degree
777
        L = min(d for n, d in G.degree())
778
        nodes = list(G)
779
        n = len(nodes)
780

    
781
        if cutoff is not None:
782
            L = min(cutoff, L)
783

    
784
        for i in range(n):
785
            kwargs['cutoff'] = L
786
            try:
787
                L = min(L, local_edge_connectivity(G, nodes[i], nodes[i + 1],
788
                                                   **kwargs))
789
            except IndexError:  # last node!
790
                L = min(L, local_edge_connectivity(G, nodes[i], nodes[0],
791
                                                   **kwargs))
792
        return L
793
    else:  # undirected
794
        # Algorithm 6 in [1]
795
        if not nx.is_connected(G):
796
            return 0
797

    
798
        # initial value for \lambda is minimum degree
799
        L = min(d for n, d in G.degree())
800

    
801
        if cutoff is not None:
802
            L = min(cutoff, L)
803

    
804
        # A dominating set is \lambda-covering
805
        # We need a dominating set with at least two nodes
806
        for node in G:
807
            D = nx.dominating_set(G, start_with=node)
808
            v = D.pop()
809
            if D:
810
                break
811
        else:
812
            # in complete graphs the dominating sets will always be of one node
813
            # thus we return min degree
814
            return L
815

    
816
        for w in D:
817
            kwargs['cutoff'] = L
818
            L = min(L, local_edge_connectivity(G, v, w, **kwargs))
819

    
820
        return L