Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (44 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Jon Crall (erotemic@gmail.com)
10
"""
11
Algorithms for finding k-edge-augmentations
12

13
A k-edge-augmentation is a set of edges, that once added to a graph, ensures
14
that the graph is k-edge-connected; i.e. the graph cannot be disconnected
15
unless k or more edges are removed.  Typically, the goal is to find the
16
augmentation with minimum weight.  In general, it is not guaranteed that a
17
k-edge-augmentation exists.
18

19
See Also
20
--------
21
:mod:`edge_kcomponents` : algorithms for finding k-edge-connected components
22
:mod:`connectivity` : algorithms for determening edge connectivity.
23
"""
24
import math
25
import sys
26
import itertools as it
27
import networkx as nx
28
from networkx.utils import not_implemented_for, py_random_state
29
from collections import defaultdict, namedtuple
30

    
31
__all__ = [
32
    'k_edge_augmentation',
33
    'is_k_edge_connected',
34
    'is_locally_k_edge_connected',
35
]
36

    
37

    
38
@not_implemented_for('directed')
39
@not_implemented_for('multigraph')
40
def is_k_edge_connected(G, k):
41
    """Tests to see if a graph is k-edge-connected.
42

43
    Is it impossible to disconnect the graph by removing fewer than k edges?
44
    If so, then G is k-edge-connected.
45

46
    Parameters
47
    ----------
48
    G : NetworkX graph
49
       An undirected graph.
50

51
    k : integer
52
        edge connectivity to test for
53

54
    Returns
55
    -------
56
    boolean
57
        True if G is k-edge-connected.
58

59
    See Also
60
    --------
61
    :func:`is_locally_k_edge_connected`
62

63
    Example
64
    -------
65
    >>> G = nx.barbell_graph(10, 0)
66
    >>> nx.is_k_edge_connected(G, k=1)
67
    True
68
    >>> nx.is_k_edge_connected(G, k=2)
69
    False
70
    """
71
    if k < 1:
72
        raise ValueError('k must be positive, not {}'.format(k))
73
    # First try to quickly determine if G is not k-edge-connected
74
    if G.number_of_nodes() < k + 1:
75
        return False
76
    elif any(d < k for n, d in G.degree()):
77
        return False
78
    else:
79
        # Otherwise perform the full check
80
        if k == 1:
81
            return nx.is_connected(G)
82
        elif k == 2:
83
            return not nx.has_bridges(G)
84
        else:
85
            return nx.edge_connectivity(G, cutoff=k) >= k
86

    
87

    
88
@not_implemented_for('directed')
89
@not_implemented_for('multigraph')
90
def is_locally_k_edge_connected(G, s, t, k):
91
    """Tests to see if an edge in a graph is locally k-edge-connected.
92

93
    Is it impossible to disconnect s and t by removing fewer than k edges?
94
    If so, then s and t are locally k-edge-connected in G.
95

96
    Parameters
97
    ----------
98
    G : NetworkX graph
99
       An undirected graph.
100

101
    s : node
102
        Source node
103

104
    t : node
105
        Target node
106

107
    k : integer
108
        local edge connectivity for nodes s and t
109

110
    Returns
111
    -------
112
    boolean
113
        True if s and t are locally k-edge-connected in G.
114

115
    See Also
116
    --------
117
    :func:`is_k_edge_connected`
118

119
    Example
120
    -------
121
    >>> from networkx.algorithms.connectivity import is_locally_k_edge_connected
122
    >>> G = nx.barbell_graph(10, 0)
123
    >>> is_locally_k_edge_connected(G, 5, 15, k=1)
124
    True
125
    >>> is_locally_k_edge_connected(G, 5, 15, k=2)
126
    False
127
    >>> is_locally_k_edge_connected(G, 1, 5, k=2)
128
    True
129
    """
130
    if k < 1:
131
        raise ValueError('k must be positive, not {}'.format(k))
132

    
133
    # First try to quickly determine s, t is not k-locally-edge-connected in G
134
    if G.degree(s) < k or G.degree(t) < k:
135
        return False
136
    else:
137
        # Otherwise perform the full check
138
        if k == 1:
139
            return nx.has_path(G, s, t)
140
        else:
141
            localk = nx.connectivity.local_edge_connectivity(G, s, t, cutoff=k)
142
            return localk >= k
143

    
144

    
145
@not_implemented_for('directed')
146
@not_implemented_for('multigraph')
147
def k_edge_augmentation(G, k, avail=None, weight=None, partial=False):
148
    """Finds set of edges to k-edge-connect G.
149

150
    Adding edges from the augmentation to G make it impossible to disconnect G
151
    unless k or more edges are removed. This function uses the most efficient
152
    function available (depending on the value of k and if the problem is
153
    weighted or unweighted) to search for a minimum weight subset of available
154
    edges that k-edge-connects G. In general, finding a k-edge-augmentation is
155
    NP-hard, so solutions are not garuenteed to be minimal. Furthermore, a
156
    k-edge-augmentation may not exist.
157

158
    Parameters
159
    ----------
160
    G : NetworkX graph
161
       An undirected graph.
162

163
    k : integer
164
        Desired edge connectivity
165

166
    avail : dict or a set of 2 or 3 tuples
167
        The available edges that can be used in the augmentation.
168

169
        If unspecified, then all edges in the complement of G are available.
170
        Otherwise, each item is an available edge (with an optional weight).
171

172
        In the unweighted case, each item is an edge ``(u, v)``.
173

174
        In the weighted case, each item is a 3-tuple ``(u, v, d)`` or a dict
175
        with items ``(u, v): d``.  The third item, ``d``, can be a dictionary
176
        or a real number.  If ``d`` is a dictionary ``d[weight]``
177
        correspondings to the weight.
178

179
    weight : string
180
        key to use to find weights if ``avail`` is a set of 3-tuples where the
181
        third item in each tuple is a dictionary.
182

183
    partial : boolean
184
        If partial is True and no feasible k-edge-augmentation exists, then all
185
        a partial k-edge-augmentation is generated. Adding the edges in a
186
        partial augmentation to G, minimizes the number of k-edge-connected
187
        components and maximizes the edge connectivity between those
188
        components. For details, see :func:`partial_k_edge_augmentation`.
189

190
    Yields
191
    ------
192
    edge : tuple
193
        Edges that, once added to G, would cause G to become k-edge-connected.
194
        If partial is False, an error is raised if this is not possible.
195
        Otherwise, generated edges form a partial augmentation, which
196
        k-edge-connects any part of G where it is possible, and maximally
197
        connects the remaining parts.
198

199
    Raises
200
    ------
201
    NetworkXUnfeasible:
202
        If partial is False and no k-edge-augmentation exists.
203

204
    NetworkXNotImplemented:
205
        If the input graph is directed or a multigraph.
206

207
    ValueError:
208
        If k is less than 1
209

210
    Notes
211
    -----
212
    When k=1 this returns an optimal solution.
213

214
    When k=2 and ``avail`` is None, this returns an optimal solution.
215
    Otherwise when k=2, this returns a 2-approximation of the optimal solution.
216

217
    For k>3, this problem is NP-hard and this uses a randomized algorithm that
218
        produces a feasible solution, but provides no guarantees on the
219
        solution weight.
220

221
    Example
222
    -------
223
    >>> # Unweighted cases
224
    >>> G = nx.path_graph((1, 2, 3, 4))
225
    >>> G.add_node(5)
226
    >>> sorted(nx.k_edge_augmentation(G, k=1))
227
    [(1, 5)]
228
    >>> sorted(nx.k_edge_augmentation(G, k=2))
229
    [(1, 5), (5, 4)]
230
    >>> sorted(nx.k_edge_augmentation(G, k=3))
231
    [(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
232
    >>> complement = list(nx.k_edge_augmentation(G, k=5, partial=True))
233
    >>> G.add_edges_from(complement)
234
    >>> nx.edge_connectivity(G)
235
    4
236

237
    Example
238
    -------
239
    >>> # Weighted cases
240
    >>> G = nx.path_graph((1, 2, 3, 4))
241
    >>> G.add_node(5)
242
    >>> # avail can be a tuple with a dict
243
    >>> avail = [(1, 5, {'weight': 11}), (2, 5, {'weight': 10})]
244
    >>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight='weight'))
245
    [(2, 5)]
246
    >>> # or avail can be a 3-tuple with a real number
247
    >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
248
    >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
249
    [(1, 5), (2, 5), (4, 5)]
250
    >>> # or avail can be a dict
251
    >>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51}
252
    >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
253
    [(1, 5), (2, 5), (4, 5)]
254
    >>> # If augmentation is infeasible, then a partial solution can be found
255
    >>> avail = {(1, 5): 11}
256
    >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True))
257
    [(1, 5)]
258
    """
259
    try:
260
        if k <= 0:
261
            raise ValueError('k must be a positive integer, not {}'.format(k))
262
        elif G.number_of_nodes() < k + 1:
263
            msg = 'impossible to {} connect in graph with less than {} nodes'
264
            raise nx.NetworkXUnfeasible(msg.format(k, k + 1))
265
        elif avail is not None and len(avail) == 0:
266
            if not nx.is_k_edge_connected(G, k):
267
                raise nx.NetworkXUnfeasible('no available edges')
268
            aug_edges = []
269
        elif k == 1:
270
            aug_edges = one_edge_augmentation(G, avail=avail, weight=weight,
271
                                              partial=partial)
272
        elif k == 2:
273
            aug_edges = bridge_augmentation(G, avail=avail, weight=weight)
274
        else:
275
            # raise NotImplementedError(
276
            #    'not implemented for k>2. k={}'.format(k))
277
            aug_edges = greedy_k_edge_augmentation(
278
                G, k=k, avail=avail, weight=weight, seed=0)
279
        # Do eager evaulation so we can catch any exceptions
280
        # Before executing partial code.
281
        for edge in list(aug_edges):
282
            yield edge
283
    except nx.NetworkXUnfeasible:
284
        if partial:
285
            # Return all available edges
286
            if avail is None:
287
                aug_edges = complement_edges(G)
288
            else:
289
                # If we can't k-edge-connect the entire graph, try to
290
                # k-edge-connect as much as possible
291
                aug_edges = partial_k_edge_augmentation(G, k=k, avail=avail,
292
                                                        weight=weight)
293
            for edge in aug_edges:
294
                yield edge
295
        else:
296
            raise
297

    
298

    
299
def partial_k_edge_augmentation(G, k, avail, weight=None):
300
    """Finds augmentation that k-edge-connects as much of the graph as possible.
301

302
    When a k-edge-augmentation is not possible, we can still try to find a
303
    small set of edges that partially k-edge-connects as much of the graph as
304
    possible. All possible edges are generated between remaining parts.
305
    This minimizes the number of k-edge-connected subgraphs in the resulting
306
    graph and maxmizes the edge connectivity between those subgraphs.
307

308
    Parameters
309
    ----------
310
    G : NetworkX graph
311
       An undirected graph.
312

313
    k : integer
314
        Desired edge connectivity
315

316
    avail : dict or a set of 2 or 3 tuples
317
        For more details, see :func:`k_edge_augmentation`.
318

319
    weight : string
320
        key to use to find weights if ``avail`` is a set of 3-tuples.
321
        For more details, see :func:`k_edge_augmentation`.
322

323
    Yields
324
    ------
325
    edge : tuple
326
        Edges in the partial augmentation of G. These edges k-edge-connect any
327
        part of G where it is possible, and maximally connects the remaining
328
        parts. In other words, all edges from avail are generated except for
329
        those within subgraphs that have already become k-edge-connected.
330

331
    Notes
332
    -----
333
    Construct H that augments G with all edges in avail.
334
    Find the k-edge-subgraphs of H.
335
    For each k-edge-subgraph, if the number of nodes is more than k, then find
336
    the k-edge-augmentation of that graph and add it to the solution. Then add
337
    all edges in avail between k-edge subgraphs to the solution.
338

339
    See Also
340
    --------
341
    :func:`k_edge_augmentation`
342

343
    Example
344
    -------
345
    >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
346
    >>> G.add_node(8)
347
    >>> avail = [(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (1, 8)]
348
    >>> sorted(partial_k_edge_augmentation(G, k=2, avail=avail))
349
    [(1, 5), (1, 8)]
350
    """
351
    def _edges_between_disjoint(H, only1, only2):
352
        """ finds edges between disjoint nodes """
353
        only1_adj = {u: set(H.adj[u]) for u in only1}
354
        for u, neighbs in only1_adj.items():
355
            # Find the neighbors of u in only1 that are also in only2
356
            neighbs12 = neighbs.intersection(only2)
357
            for v in neighbs12:
358
                yield (u, v)
359

    
360
    avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G)
361

    
362
    # Find which parts of the graph can be k-edge-connected
363
    H = G.copy()
364
    H.add_edges_from(
365
        ((u, v, {'weight': w, 'generator': (u, v)})
366
         for (u, v), w in zip(avail, avail_w)))
367
    k_edge_subgraphs = list(nx.k_edge_subgraphs(H, k=k))
368

    
369
    # Generate edges to k-edge-connect internal subgraphs
370
    for nodes in k_edge_subgraphs:
371
        if len(nodes) > 1:
372
            # Get the k-edge-connected subgraph
373
            C = H.subgraph(nodes).copy()
374
            # Find the internal edges that were available
375
            sub_avail = {
376
                d['generator']: d['weight']
377
                for (u, v, d) in C.edges(data=True)
378
                if 'generator' in d
379
            }
380
            # Remove potential augmenting edges
381
            C.remove_edges_from(sub_avail.keys())
382
            # Find a subset of these edges that makes the compoment
383
            # k-edge-connected and ignore the rest
384
            for edge in nx.k_edge_augmentation(C, k=k, avail=sub_avail):
385
                yield edge
386

    
387
    # Generate all edges between CCs that could not be k-edge-connected
388
    for cc1, cc2 in it.combinations(k_edge_subgraphs, 2):
389
        for (u, v) in _edges_between_disjoint(H, cc1, cc2):
390
            d = H.get_edge_data(u, v)
391
            edge = d.get('generator', None)
392
            if edge is not None:
393
                yield edge
394

    
395

    
396
@not_implemented_for('multigraph')
397
@not_implemented_for('directed')
398
def one_edge_augmentation(G, avail=None, weight=None, partial=False):
399
    """Finds minimum weight set of edges to connect G.
400

401
    Equivalent to :func:`k_edge_augmentation` when k=1. Adding the resulting
402
    edges to G will make it 1-edge-connected. The solution is optimal for both
403
    weighted and non-weighted variants.
404

405
    Parameters
406
    ----------
407
    G : NetworkX graph
408
       An undirected graph.
409

410
    avail : dict or a set of 2 or 3 tuples
411
        For more details, see :func:`k_edge_augmentation`.
412

413
    weight : string
414
        key to use to find weights if ``avail`` is a set of 3-tuples.
415
        For more details, see :func:`k_edge_augmentation`.
416

417
    partial : boolean
418
        If partial is True and no feasible k-edge-augmentation exists, then the
419
        augmenting edges minimize the number of connected components.
420

421
    Yields
422
    ------
423
    edge : tuple
424
        Edges in the one-augmentation of G
425

426
    Raises
427
    ------
428
    NetworkXUnfeasible:
429
        If partial is False and no one-edge-augmentation exists.
430

431
    Notes
432
    -----
433
    Uses either :func:`unconstrained_one_edge_augmentation` or
434
    :func:`weighted_one_edge_augmentation` depending on whether ``avail`` is
435
    specified. Both algorithms are based on finding a minimum spanning tree.
436
    As such both algorithms find optimal solutions and run in linear time.
437

438
    See Also
439
    --------
440
    :func:`k_edge_augmentation`
441
    """
442
    if avail is None:
443
        return unconstrained_one_edge_augmentation(G)
444
    else:
445
        return weighted_one_edge_augmentation(G, avail=avail, weight=weight,
446
                                              partial=partial)
447

    
448

    
449
@not_implemented_for('multigraph')
450
@not_implemented_for('directed')
451
def bridge_augmentation(G, avail=None, weight=None):
452
    """Finds the a set of edges that bridge connects G.
453

454
    Equivalent to :func:`k_edge_augmentation` when k=2, and partial=False.
455
    Adding the resulting edges to G will make it 2-edge-connected.  If no
456
    constraints are specified the returned set of edges is minimum an optimal,
457
    otherwise the solution is approximated.
458

459
    Parameters
460
    ----------
461
    G : NetworkX graph
462
       An undirected graph.
463

464
    avail : dict or a set of 2 or 3 tuples
465
        For more details, see :func:`k_edge_augmentation`.
466

467
    weight : string
468
        key to use to find weights if ``avail`` is a set of 3-tuples.
469
        For more details, see :func:`k_edge_augmentation`.
470

471
    Yields
472
    ------
473
    edge : tuple
474
        Edges in the bridge-augmentation of G
475

476
    Raises
477
    ------
478
    NetworkXUnfeasible:
479
        If no bridge-augmentation exists.
480

481
    Notes
482
    -----
483
    If there are no constraints the solution can be computed in linear time
484
    using :func:`unconstrained_bridge_augmentation`. Otherwise, the problem
485
    becomes NP-hard and is the solution is approximated by
486
    :func:`weighted_bridge_augmentation`.
487

488
    See Also
489
    --------
490
    :func:`k_edge_augmentation`
491
    """
492
    if G.number_of_nodes() < 3:
493
        raise nx.NetworkXUnfeasible(
494
            'impossible to bridge connect less than 3 nodes')
495
    if avail is None:
496
        return unconstrained_bridge_augmentation(G)
497
    else:
498
        return weighted_bridge_augmentation(G, avail, weight=weight)
499

    
500

    
501
# --- Algorithms and Helpers ---
502

    
503
def _ordered(u, v):
504
    """Returns the nodes in an undirected edge in lower-triangular order"""
505
    return (u, v) if u < v else (v, u)
506

    
507

    
508
def _unpack_available_edges(avail, weight=None, G=None):
509
    """Helper to separate avail into edges and corresponding weights"""
510
    if weight is None:
511
        weight = 'weight'
512
    if isinstance(avail, dict):
513
        avail_uv = list(avail.keys())
514
        avail_w = list(avail.values())
515
    else:
516
        def _try_getitem(d):
517
            try:
518
                return d[weight]
519
            except TypeError:
520
                return d
521
        avail_uv = [tup[0:2] for tup in avail]
522
        avail_w = [1 if len(tup) == 2 else _try_getitem(tup[-1])
523
                   for tup in avail]
524

    
525
    if G is not None:
526
        # Edges already in the graph are filtered
527
        flags = [not G.has_edge(u, v) for u, v in avail_uv]
528
        avail_uv = list(it.compress(avail_uv, flags))
529
        avail_w = list(it.compress(avail_w, flags))
530
    return avail_uv, avail_w
531

    
532

    
533
MetaEdge = namedtuple('MetaEdge', ('meta_uv', 'uv', 'w'))
534

    
535

    
536
def _lightest_meta_edges(mapping, avail_uv, avail_w):
537
    """Maps available edges in the original graph to edges in the metagraph.
538

539
    Parameters
540
    ----------
541
    mapping : dict
542
        mapping produced by :func:`collapse`, that maps each node in the
543
        original graph to a node in the meta graph
544

545
    avail_uv : list
546
        list of edges
547

548
    avail_w : list
549
        list of edge weights
550

551
    Notes
552
    -----
553
    Each node in the metagraph is a k-edge-connected component in the original
554
    graph.  We don't care about any edge within the same k-edge-connected
555
    component, so we ignore self edges.  We also are only intereseted in the
556
    minimum weight edge bridging each k-edge-connected component so, we group
557
    the edges by meta-edge and take the lightest in each group.
558

559
    Example
560
    -------
561
    >>> # Each group represents a meta-node
562
    >>> groups = ([1, 2, 3], [4, 5], [6])
563
    >>> mapping = {n: meta_n for meta_n, ns in enumerate(groups) for n in ns}
564
    >>> avail_uv = [(1, 2), (3, 6), (1, 4), (5, 2), (6, 1), (2, 6), (3, 1)]
565
    >>> avail_w =  [    20,     99,     20,     15,     50,     99,     20]
566
    >>> sorted(_lightest_meta_edges(mapping, avail_uv, avail_w))
567
    [MetaEdge(meta_uv=(0, 1), uv=(5, 2), w=15), MetaEdge(meta_uv=(0, 2), uv=(6, 1), w=50)]
568
    """
569
    grouped_wuv = defaultdict(list)
570
    for w, (u, v) in zip(avail_w, avail_uv):
571
        # Order the meta-edge so it can be used as a dict key
572
        meta_uv = _ordered(mapping[u], mapping[v])
573
        # Group each available edge using the meta-edge as a key
574
        grouped_wuv[meta_uv].append((w, u, v))
575

    
576
    # Now that all available edges are grouped, choose one per group
577
    for (mu, mv), choices_wuv in grouped_wuv.items():
578
        # Ignore available edges within the same meta-node
579
        if mu != mv:
580
            # Choose the lightest available edge belonging to each meta-edge
581
            w, u, v = min(choices_wuv)
582
            yield MetaEdge((mu, mv), (u, v), w)
583

    
584

    
585
def unconstrained_one_edge_augmentation(G):
586
    """Finds the smallest set of edges to connect G.
587

588
    This is a variant of the unweighted MST problem.
589
    If G is not empty, a feasible solution always exists.
590

591
    Parameters
592
    ----------
593
    G : NetworkX graph
594
       An undirected graph.
595

596
    Yields
597
    ------
598
    edge : tuple
599
        Edges in the one-edge-augmentation of G
600

601
    See Also
602
    --------
603
    :func:`one_edge_augmentation`
604
    :func:`k_edge_augmentation`
605

606
    Example
607
    -------
608
    >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
609
    >>> G.add_nodes_from([6, 7, 8])
610
    >>> sorted(unconstrained_one_edge_augmentation(G))
611
    [(1, 4), (4, 6), (6, 7), (7, 8)]
612
    """
613
    ccs1 = list(nx.connected_components(G))
614
    C = collapse(G, ccs1)
615
    # When we are not constrained, we can just make a meta graph tree.
616
    meta_nodes = list(C.nodes())
617
    # build a path in the metagraph
618
    meta_aug = list(zip(meta_nodes, meta_nodes[1:]))
619
    # map that path to the original graph
620
    inverse = defaultdict(list)
621
    for k, v in C.graph['mapping'].items():
622
        inverse[v].append(k)
623
    for mu, mv in meta_aug:
624
        yield (inverse[mu][0], inverse[mv][0])
625

    
626

    
627
def weighted_one_edge_augmentation(G, avail, weight=None, partial=False):
628
    """Finds the minimum weight set of edges to connect G if one exists.
629

630
    This is a variant of the weighted MST problem.
631

632
    Parameters
633
    ----------
634
    G : NetworkX graph
635
       An undirected graph.
636

637
    avail : dict or a set of 2 or 3 tuples
638
        For more details, see :func:`k_edge_augmentation`.
639

640
    weight : string
641
        key to use to find weights if ``avail`` is a set of 3-tuples.
642
        For more details, see :func:`k_edge_augmentation`.
643

644
    partial : boolean
645
        If partial is True and no feasible k-edge-augmentation exists, then the
646
        augmenting edges minimize the number of connected components.
647

648
    Yields
649
    ------
650
    edge : tuple
651
        Edges in the subset of avail chosen to connect G.
652

653
    See Also
654
    --------
655
    :func:`one_edge_augmentation`
656
    :func:`k_edge_augmentation`
657

658
    Example
659
    -------
660
    >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
661
    >>> G.add_nodes_from([6, 7, 8])
662
    >>> # any edge not in avail has an implicit weight of infinity
663
    >>> avail = [(1, 3), (1, 5), (4, 7), (4, 8), (6, 1), (8, 1), (8, 2)]
664
    >>> sorted(weighted_one_edge_augmentation(G, avail))
665
    [(1, 5), (4, 7), (6, 1), (8, 1)]
666
    >>> # find another solution by giving large weights to edges in the
667
    >>> # previous solution (note some of the old edges must be used)
668
    >>> avail = [(1, 3), (1, 5, 99), (4, 7, 9), (6, 1, 99), (8, 1, 99), (8, 2)]
669
    >>> sorted(weighted_one_edge_augmentation(G, avail))
670
    [(1, 5), (4, 7), (6, 1), (8, 2)]
671
    """
672
    avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G)
673
    # Collapse CCs in the original graph into nodes in a metagraph
674
    # Then find an MST of the metagraph instead of the original graph
675
    C = collapse(G, nx.connected_components(G))
676
    mapping = C.graph['mapping']
677
    # Assign each available edge to an edge in the metagraph
678
    candidate_mapping = _lightest_meta_edges(mapping, avail_uv, avail_w)
679
    # nx.set_edge_attributes(C, name='weight', values=0)
680
    C.add_edges_from(
681
        (mu, mv, {'weight': w, 'generator': uv})
682
        for (mu, mv), uv, w in candidate_mapping
683
    )
684
    # Find MST of the meta graph
685
    meta_mst = nx.minimum_spanning_tree(C)
686
    if not partial and not nx.is_connected(meta_mst):
687
        raise nx.NetworkXUnfeasible(
688
            'Not possible to connect G with available edges')
689
    # Yield the edge that generated the meta-edge
690
    for mu, mv, d in meta_mst.edges(data=True):
691
        if 'generator' in d:
692
            edge = d['generator']
693
            yield edge
694

    
695

    
696
def unconstrained_bridge_augmentation(G):
697
    """Finds an optimal 2-edge-augmentation of G using the fewest edges.
698

699
    This is an implementation of the algorithm detailed in [1]_.
700
    The basic idea is to construct a meta-graph of bridge-ccs, connect leaf
701
    nodes of the trees to connect the entire graph, and finally connect the
702
    leafs of the tree in dfs-preorder to bridge connect the entire graph.
703

704
    Parameters
705
    ----------
706
    G : NetworkX graph
707
       An undirected graph.
708

709
    Yields
710
    ------
711
    edge : tuple
712
        Edges in the bridge augmentation of G
713

714
    Notes
715
    -----
716
    Input: a graph G.
717
    First find the bridge components of G and collapse each bridge-cc into a
718
    node of a metagraph graph C, which is guaranteed to be a forest of trees.
719

720
    C contains p "leafs" --- nodes with exactly one incident edge.
721
    C contains q "isolated nodes" --- nodes with no incident edges.
722

723
    Theorem: If p + q > 1, then at least :math:`ceil(p / 2) + q` edges are
724
        needed to bridge connect C. This algorithm achieves this min number.
725

726
    The method first adds enough edges to make G into a tree and then pairs
727
    leafs in a simple fashion.
728

729
    Let n be the number of trees in C. Let v(i) be an isolated vertex in the
730
    i-th tree if one exists, otherwise it is a pair of distinct leafs nodes
731
    in the i-th tree. Alternating edges from these sets (i.e.  adding edges
732
    A1 = [(v(i)[0], v(i + 1)[1]), v(i + 1)[0], v(i + 2)[1])...]) connects C
733
    into a tree T. This tree has p' = p + 2q - 2(n -1) leafs and no isolated
734
    vertices. A1 has n - 1 edges. The next step finds ceil(p' / 2) edges to
735
    biconnect any tree with p' leafs.
736

737
    Convert T into an arborescence T' by picking an arbitrary root node with
738
    degree >= 2 and directing all edges away from the root. Note the
739
    implementation implicitly constructs T'.
740

741
    The leafs of T are the nodes with no existing edges in T'.
742
    Order the leafs of T' by DFS prorder. Then break this list in half
743
    and add the zipped pairs to A2.
744

745
    The set A = A1 + A2 is the minimum augmentation in the metagraph.
746

747
    To convert this to edges in the original graph
748

749
    References
750
    ----------
751
    .. [1] Eswaran, Kapali P., and R. Endre Tarjan. (1975) Augmentation problems.
752
        http://epubs.siam.org/doi/abs/10.1137/0205044
753

754
    See Also
755
    --------
756
    :func:`bridge_augmentation`
757
    :func:`k_edge_augmentation`
758

759
    Example
760
    -------
761
    >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
762
    >>> sorted(unconstrained_bridge_augmentation(G))
763
    [(1, 7)]
764
    >>> G = nx.path_graph((1, 2, 3, 2, 4, 5, 6, 7))
765
    >>> sorted(unconstrained_bridge_augmentation(G))
766
    [(1, 3), (3, 7)]
767
    >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
768
    >>> G.add_node(4)
769
    >>> sorted(unconstrained_bridge_augmentation(G))
770
    [(1, 4), (4, 0)]
771
    """
772
    # -----
773
    # Mapping of terms from (Eswaran and Tarjan):
774
    #     G = G_0 - the input graph
775
    #     C = G_0' - the bridge condensation of G. (This is a forest of trees)
776
    #     A1 = A_1 - the edges to connect the forest into a tree
777
    #         leaf = pendant - a node with degree of 1
778

    
779
    #     alpha(v) = maps the node v in G to its meta-node in C
780
    #     beta(x) = maps the meta-node x in C to any node in the bridge
781
    #         component of G corresponding to x.
782

    
783
    # find the 2-edge-connected components of G
784
    bridge_ccs = list(nx.connectivity.bridge_components(G))
785
    # condense G into an forest C
786
    C = collapse(G, bridge_ccs)
787

    
788
    # Choose pairs of distinct leaf nodes in each tree. If this is not
789
    # possible then make a pair using the single isolated node in the tree.
790
    vset1 = [
791
        tuple(cc) * 2   # case1: an isolated node
792
        if len(cc) == 1 else
793
        sorted(cc, key=C.degree)[0:2]  # case2: pair of leaf nodes
794
        for cc in nx.connected_components(C)
795
    ]
796
    if len(vset1) > 1:
797
        # Use this set to construct edges that connect C into a tree.
798
        nodes1 = [vs[0] for vs in vset1]
799
        nodes2 = [vs[1] for vs in vset1]
800
        A1 = list(zip(nodes1[1:], nodes2))
801
    else:
802
        A1 = []
803
    # Connect each tree in the forest to construct an arborescence
804
    T = C.copy()
805
    T.add_edges_from(A1)
806

    
807
    # If there are only two leaf nodes, we simply connect them.
808
    leafs = [n for n, d in T.degree() if d == 1]
809
    if len(leafs) == 1:
810
        A2 = []
811
    if len(leafs) == 2:
812
        A2 = [tuple(leafs)]
813
    else:
814
        # Choose an arbitrary non-leaf root
815
        try:
816
            root = next(n for n, d in T.degree() if d > 1)
817
        except StopIteration:  # no nodes found with degree > 1
818
            return
819
        # order the leaves of C by (induced directed) preorder
820
        v2 = [n for n in nx.dfs_preorder_nodes(T, root) if T.degree(n) == 1]
821
        # connecting first half of the leafs in pre-order to the second
822
        # half will bridge connect the tree with the fewest edges.
823
        half = int(math.ceil(len(v2) / 2.0))
824
        A2 = list(zip(v2[:half], v2[-half:]))
825

    
826
    # collect the edges used to augment the original forest
827
    aug_tree_edges = A1 + A2
828

    
829
    # Construct the mapping (beta) from meta-nodes to regular nodes
830
    inverse = defaultdict(list)
831
    for k, v in C.graph['mapping'].items():
832
        inverse[v].append(k)
833
    # sort so we choose minimum degree nodes first
834
    inverse = {mu: sorted(mapped, key=lambda u: (G.degree(u), u))
835
               for mu, mapped in inverse.items()}
836

    
837
    # For each meta-edge, map back to an arbitrary pair in the original graph
838
    G2 = G.copy()
839
    for mu, mv in aug_tree_edges:
840
        # Find the first available edge that doesn't exist and return it
841
        for u, v in it.product(inverse[mu], inverse[mv]):
842
            if not G2.has_edge(u, v):
843
                G2.add_edge(u, v)
844
                yield u, v
845
                break
846

    
847

    
848
def weighted_bridge_augmentation(G, avail, weight=None):
849
    """Finds an approximate min-weight 2-edge-augmentation of G.
850

851
    This is an implementation of the approximation algorithm detailed in [1]_.
852
    It chooses a set of edges from avail to add to G that renders it
853
    2-edge-connected if such a subset exists.  This is done by finding a
854
    minimum spanning arborescence of a specially constructed metagraph.
855

856
    Parameters
857
    ----------
858
    G : NetworkX graph
859
       An undirected graph.
860

861
    avail : set of 2 or 3 tuples.
862
        candidate edges (with optional weights) to choose from
863

864
    weight : string
865
        key to use to find weights if avail is a set of 3-tuples where the
866
        third item in each tuple is a dictionary.
867

868
    Yields
869
    ------
870
    edge : tuple
871
        Edges in the subset of avail chosen to bridge augment G.
872

873
    Notes
874
    -----
875
    Finding a weighted 2-edge-augmentation is NP-hard.
876
    Any edge not in ``avail`` is considered to have a weight of infinity.
877
    The approximation factor is 2 if ``G`` is connected and 3 if it is not.
878
    Runs in :math:`O(m + n log(n))` time
879

880
    References
881
    ----------
882
    .. [1] Khuller, Samir, and Ramakrishna Thurimella. (1993) Approximation
883
        algorithms for graph augmentation.
884
        http://www.sciencedirect.com/science/article/pii/S0196677483710102
885

886
    See Also
887
    --------
888
    :func:`bridge_augmentation`
889
    :func:`k_edge_augmentation`
890

891
    Example
892
    -------
893
    >>> G = nx.path_graph((1, 2, 3, 4))
894
    >>> # When the weights are equal, (1, 4) is the best
895
    >>> avail = [(1, 4, 1), (1, 3, 1), (2, 4, 1)]
896
    >>> sorted(weighted_bridge_augmentation(G, avail))
897
    [(1, 4)]
898
    >>> # Giving (1, 4) a high weight makes the two edge solution the best.
899
    >>> avail = [(1, 4, 1000), (1, 3, 1), (2, 4, 1)]
900
    >>> sorted(weighted_bridge_augmentation(G, avail))
901
    [(1, 3), (2, 4)]
902
    >>> #------
903
    >>> G = nx.path_graph((1, 2, 3, 4))
904
    >>> G.add_node(5)
905
    >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 1)]
906
    >>> sorted(weighted_bridge_augmentation(G, avail=avail))
907
    [(1, 5), (4, 5)]
908
    >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
909
    >>> sorted(weighted_bridge_augmentation(G, avail=avail))
910
    [(1, 5), (2, 5), (4, 5)]
911
    """
912

    
913
    if weight is None:
914
        weight = 'weight'
915

    
916
    # If input G is not connected the approximation factor increases to 3
917
    if not nx.is_connected(G):
918
        H = G.copy()
919
        connectors = list(one_edge_augmentation(H, avail=avail, weight=weight))
920
        H.add_edges_from(connectors)
921

    
922
        for edge in connectors:
923
            yield edge
924
    else:
925
        connectors = []
926
        H = G
927

    
928
    if len(avail) == 0:
929
        if nx.has_bridges(H):
930
            raise nx.NetworkXUnfeasible('no augmentation possible')
931

    
932
    avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=H)
933

    
934
    # Collapse input into a metagraph. Meta nodes are bridge-ccs
935
    bridge_ccs = nx.connectivity.bridge_components(H)
936
    C = collapse(H, bridge_ccs)
937

    
938
    # Use the meta graph to shrink avail to a small feasible subset
939
    mapping = C.graph['mapping']
940
    # Choose the minimum weight feasible edge in each group
941
    meta_to_wuv = {
942
        (mu, mv): (w, uv)
943
        for (mu, mv), uv, w in _lightest_meta_edges(mapping, avail_uv, avail_w)
944
    }
945

    
946
    # Mapping of terms from (Khuller and Thurimella):
947
    #     C         : G_0 = (V, E^0)
948
    #        This is the metagraph where each node is a 2-edge-cc in G.
949
    #        The edges in C represent bridges in the original graph.
950
    #     (mu, mv)  : E - E^0  # they group both avail and given edges in E
951
    #     T         : \Gamma
952
    #     D         : G^D = (V, E_D)
953

    
954
    #     The paper uses ancestor because children point to parents, which is
955
    #     contrary to networkx standards.  So, we actually need to run
956
    #     nx.least_common_ancestor on the reversed Tree.
957

    
958
    # Pick an arbitrary leaf from C as the root
959
    try:
960
        root = next(n for n, d in C.degree() if d == 1)
961
    except StopIteration:  # no nodes found with degree == 1
962
        return
963
    # Root C into a tree TR by directing all edges away from the root
964
    # Note in their paper T directs edges towards the root
965
    TR = nx.dfs_tree(C, root)
966

    
967
    # Add to D the directed edges of T and set their weight to zero
968
    # This indicates that it costs nothing to use edges that were given.
969
    D = nx.reverse(TR).copy()
970

    
971
    nx.set_edge_attributes(D, name='weight', values=0)
972

    
973
    # The LCA of mu and mv in T is the shared ancestor of mu and mv that is
974
    # located farthest from the root.
975
    lca_gen = nx.tree_all_pairs_lowest_common_ancestor(
976
        TR, root=root, pairs=meta_to_wuv.keys())
977

    
978
    for (mu, mv), lca in lca_gen:
979
        w, uv = meta_to_wuv[(mu, mv)]
980
        if lca == mu:
981
            # If u is an ancestor of v in TR, then add edge u->v to D
982
            D.add_edge(lca, mv, weight=w, generator=uv)
983
        elif lca == mv:
984
            # If v is an ancestor of u in TR, then add edge v->u to D
985
            D.add_edge(lca, mu, weight=w, generator=uv)
986
        else:
987
            # If neither u nor v is a ancestor of the other in TR
988
            # let t = lca(TR, u, v) and add edges t->u and t->v
989
            # Track the original edge that GENERATED these edges.
990
            D.add_edge(lca, mu, weight=w, generator=uv)
991
            D.add_edge(lca, mv, weight=w, generator=uv)
992

    
993
    # Then compute a minimum rooted branching
994
    try:
995
        # Note the original edges must be directed towards to root for the
996
        # branching to give us a bridge-augmentation.
997
        A = _minimum_rooted_branching(D, root)
998
    except nx.NetworkXException:
999
        # If there is no branching then augmentation is not possible
1000
        raise nx.NetworkXUnfeasible('no 2-edge-augmentation possible')
1001

    
1002
    # For each edge e, in the branching that did not belong to the directed
1003
    # tree T, add the corresponding edge that **GENERATED** it (this is not
1004
    # necesarilly e itself!)
1005

    
1006
    # ensure the third case does not generate edges twice
1007
    bridge_connectors = set()
1008
    for mu, mv in A.edges():
1009
        data = D.get_edge_data(mu, mv)
1010
        if 'generator' in data:
1011
            # Add the avail edge that generated the branching edge.
1012
            edge = data['generator']
1013
            bridge_connectors.add(edge)
1014

    
1015
    for edge in bridge_connectors:
1016
        yield edge
1017

    
1018

    
1019
def _minimum_rooted_branching(D, root):
1020
    """Helper function to compute a minimum rooted branching (aka rooted
1021
    arborescence)
1022

1023
    Before the branching can be computed, the directed graph must be rooted by
1024
    removing the predecessors of root.
1025

1026
    A branching / arborescence of rooted graph G is a subgraph that contains a
1027
    directed path from the root to every other vertex. It is the directed
1028
    analog of the minimum spanning tree problem.
1029

1030
    References
1031
    ----------
1032
    [1] Khuller, Samir (2002) Advanced Algorithms Lecture 24 Notes.
1033
    https://www.cs.umd.edu/class/spring2011/cmsc651/lec07.pdf
1034
    """
1035
    rooted = D.copy()
1036
    # root the graph by removing all predecessors to `root`.
1037
    rooted.remove_edges_from([(u, root) for u in D.predecessors(root)])
1038
    # Then compute the branching / arborescence.
1039
    A = nx.minimum_spanning_arborescence(rooted)
1040
    return A
1041

    
1042

    
1043
def collapse(G, grouped_nodes):
1044
    """Collapses each group of nodes into a single node.
1045

1046
    This is similar to condensation, but works on undirected graphs.
1047

1048
    Parameters
1049
    ----------
1050
    G : NetworkX Graph
1051

1052
    grouped_nodes:  list or generator
1053
       Grouping of nodes to collapse. The grouping must be disjoint.
1054
       If grouped_nodes are strongly_connected_components then this is
1055
       equivalent to :func:`condensation`.
1056

1057
    Returns
1058
    -------
1059
    C : NetworkX Graph
1060
       The collapsed graph C of G with respect to the node grouping.  The node
1061
       labels are integers corresponding to the index of the component in the
1062
       list of grouped_nodes.  C has a graph attribute named 'mapping' with a
1063
       dictionary mapping the original nodes to the nodes in C to which they
1064
       belong.  Each node in C also has a node attribute 'members' with the set
1065
       of original nodes in G that form the group that the node in C
1066
       represents.
1067

1068
    Examples
1069
    --------
1070
    >>> # Collapses a graph using disjoint groups, but not necesarilly connected
1071
    >>> G = nx.Graph([(1, 0), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (5, 7)])
1072
    >>> G.add_node('A')
1073
    >>> grouped_nodes = [{0, 1, 2, 3}, {5, 6, 7}]
1074
    >>> C = collapse(G, grouped_nodes)
1075
    >>> members = nx.get_node_attributes(C, 'members')
1076
    >>> sorted(members.keys())
1077
    [0, 1, 2, 3]
1078
    >>> member_values = set(map(frozenset, members.values()))
1079
    >>> assert {0, 1, 2, 3} in member_values
1080
    >>> assert {4} in member_values
1081
    >>> assert {5, 6, 7} in member_values
1082
    >>> assert {'A'} in member_values
1083
    """
1084
    mapping = {}
1085
    members = {}
1086
    C = G.__class__()
1087
    i = 0  # required if G is empty
1088
    remaining = set(G.nodes())
1089
    for i, group in enumerate(grouped_nodes):
1090
        group = set(group)
1091
        assert remaining.issuperset(group), (
1092
            'grouped nodes must exist in G and be disjoint')
1093
        remaining.difference_update(group)
1094
        members[i] = group
1095
        mapping.update((n, i) for n in group)
1096
    # remaining nodes are in their own group
1097
    for i, node in enumerate(remaining, start=i + 1):
1098
        group = set([node])
1099
        members[i] = group
1100
        mapping.update((n, i) for n in group)
1101
    number_of_groups = i + 1
1102
    C.add_nodes_from(range(number_of_groups))
1103
    C.add_edges_from((mapping[u], mapping[v]) for u, v in G.edges()
1104
                     if mapping[u] != mapping[v])
1105
    # Add a list of members (ie original nodes) to each node (ie scc) in C.
1106
    nx.set_node_attributes(C, name='members', values=members)
1107
    # Add mapping dict as graph attribute
1108
    C.graph['mapping'] = mapping
1109
    return C
1110

    
1111

    
1112
def complement_edges(G):
1113
    """Returns only the edges in the complement of G
1114

1115
    Parameters
1116
    ----------
1117
    G : NetworkX Graph
1118

1119
    Yields
1120
    ------
1121
    edge : tuple
1122
        Edges in the complement of G
1123

1124
    Example
1125
    -------
1126
    >>> G = nx.path_graph((1, 2, 3, 4))
1127
    >>> sorted(complement_edges(G))
1128
    [(1, 3), (1, 4), (2, 4)]
1129
    >>> G = nx.path_graph((1, 2, 3, 4), nx.DiGraph())
1130
    >>> sorted(complement_edges(G))
1131
    [(1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)]
1132
    >>> G = nx.complete_graph(1000)
1133
    >>> sorted(complement_edges(G))
1134
    []
1135
    """
1136
    if G.is_directed():
1137
        for u, v in it.combinations(G.nodes(), 2):
1138
            if v not in G.adj[u]:
1139
                yield (u, v)
1140
            if u not in G.adj[v]:
1141
                yield (v, u)
1142
    else:
1143
        for u, v in it.combinations(G.nodes(), 2):
1144
            if v not in G.adj[u]:
1145
                yield (u, v)
1146

    
1147

    
1148
if sys.version_info[0] == 2:
1149
    def _compat_shuffle(rng, input):
1150
        """
1151
        python2 workaround so shuffle works the same as python3
1152

1153
        References
1154
        ----------
1155
        https://stackoverflow.com/questions/38943038/diff-shuffle-py2-py3
1156
        """
1157
        def _randbelow(n):
1158
            "Return a random int in the range [0,n). Raises ValueError if n==0."
1159
            getrandbits = rng.getrandbits
1160
            k = n.bit_length()  # don't use (n-1) here because n can be 1
1161
            r = getrandbits(k)  # 0 <= r < 2**k
1162
            while r >= n:
1163
                r = getrandbits(k)
1164
            return r
1165

    
1166
        for i in range(len(input) - 1, 0, -1):
1167
            # pick an element in input[:i+1] with which to exchange input[i]
1168
            j = _randbelow(i + 1)
1169
            input[i], input[j] = input[j], input[i]
1170
else:
1171
    def _compat_shuffle(rng, input):
1172
        """wrapper around rng.shuffle for python 2 compatibility reasons"""
1173
        rng.shuffle(input)
1174

    
1175

    
1176
@py_random_state(4)
1177
@not_implemented_for('multigraph')
1178
@not_implemented_for('directed')
1179
def greedy_k_edge_augmentation(G, k, avail=None, weight=None, seed=None):
1180
    """Greedy algorithm for finding a k-edge-augmentation
1181

1182
    Parameters
1183
    ----------
1184
    G : NetworkX graph
1185
       An undirected graph.
1186

1187
    k : integer
1188
        Desired edge connectivity
1189

1190
    avail : dict or a set of 2 or 3 tuples
1191
        For more details, see :func:`k_edge_augmentation`.
1192

1193
    weight : string
1194
        key to use to find weights if ``avail`` is a set of 3-tuples.
1195
        For more details, see :func:`k_edge_augmentation`.
1196

1197
    seed : integer, random_state, or None (default)
1198
        Indicator of random number generation state.
1199
        See :ref:`Randomness<randomness>`.
1200

1201
    Yields
1202
    ------
1203
    edge : tuple
1204
        Edges in the greedy augmentation of G
1205

1206
    Notes
1207
    -----
1208
    The algorithm is simple. Edges are incrementally added between parts of the
1209
    graph that are not yet locally k-edge-connected. Then edges are from the
1210
    augmenting set are pruned as long as local-edge-connectivity is not broken.
1211

1212
    This algorithm is greedy and does not provide optimality guarantees. It
1213
    exists only to provide :func:`k_edge_augmentation` with the ability to
1214
    generate a feasible solution for arbitrary k.
1215

1216
    See Also
1217
    --------
1218
    :func:`k_edge_augmentation`
1219

1220
    Example
1221
    -------
1222
    >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
1223
    >>> sorted(greedy_k_edge_augmentation(G, k=2))
1224
    [(1, 7)]
1225
    >>> sorted(greedy_k_edge_augmentation(G, k=1, avail=[]))
1226
    []
1227
    >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
1228
    >>> avail = {(u, v): 1 for (u, v) in complement_edges(G)}
1229
    >>> # randomized pruning process can produce different solutions
1230
    >>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=2))
1231
    [(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 4), (2, 6), (3, 7), (5, 7)]
1232
    >>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=3))
1233
    [(1, 3), (1, 5), (1, 6), (2, 4), (2, 6), (3, 7), (4, 7), (5, 7)]
1234
    """
1235
    # Result set
1236
    aug_edges = []
1237

    
1238
    done = is_k_edge_connected(G, k)
1239
    if done:
1240
        return
1241
    if avail is None:
1242
        # all edges are available
1243
        avail_uv = list(complement_edges(G))
1244
        avail_w = [1] * len(avail_uv)
1245
    else:
1246
        # Get the unique set of unweighted edges
1247
        avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G)
1248

    
1249
    # Greedy: order lightest edges. Use degree sum to tie-break
1250
    tiebreaker = [sum(map(G.degree, uv)) for uv in avail_uv]
1251
    avail_wduv = sorted(zip(avail_w, tiebreaker, avail_uv))
1252
    avail_uv = [uv for w, d, uv in avail_wduv]
1253

    
1254
    # Incrementally add edges in until we are k-connected
1255
    H = G.copy()
1256
    for (u, v) in avail_uv:
1257
        done = False
1258
        if not is_locally_k_edge_connected(H, u, v, k=k):
1259
            # Only add edges in parts that are not yet locally k-edge-connected
1260
            aug_edges.append((u, v))
1261
            H.add_edge(u, v)
1262
            # Did adding this edge help?
1263
            if H.degree(u) >= k and H.degree(v) >= k:
1264
                done = is_k_edge_connected(H, k)
1265
        if done:
1266
            break
1267

    
1268
    # Check for feasibility
1269
    if not done:
1270
        raise nx.NetworkXUnfeasible(
1271
            'not able to k-edge-connect with available edges')
1272

    
1273
    # Randomized attempt to reduce the size of the solution
1274
    _compat_shuffle(seed, aug_edges)
1275
    for (u, v) in list(aug_edges):
1276
        # Don't remove if we know it would break connectivity
1277
        if H.degree(u) <= k or H.degree(v) <= k:
1278
            continue
1279
        H.remove_edge(u, v)
1280
        aug_edges.remove((u, v))
1281
        if not is_k_edge_connected(H, k=k):
1282
            # If removing this edge breaks feasibility, undo
1283
            H.add_edge(u, v)
1284
            aug_edges.append((u, v))
1285

    
1286
    # Generate results
1287
    for edge in aug_edges:
1288
        yield edge