# networkx.algorithms.connectivity.edge_augmentation.k_edge_augmentation¶

k_edge_augmentation(G, k, avail=None, weight=None, partial=False)[source]

Finds set of edges to k-edge-connect G.

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

Parameters
GNetworkX graph

An undirected graph.

kinteger

Desired edge connectivity

availdict or a set of 2 or 3 tuples

The available edges that can be used in the augmentation.

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

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

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

weightstring

key to use to find weights if `avail` is a set of 3-tuples where the third item in each tuple is a dictionary.

partialboolean

If partial is True and no feasible k-edge-augmentation exists, then all a partial k-edge-augmentation is generated. Adding the edges in a partial augmentation to G, minimizes the number of k-edge-connected components and maximizes the edge connectivity between those components. For details, see `partial_k_edge_augmentation()`.

Yields
edgetuple

Edges that, once added to G, would cause G to become k-edge-connected. If partial is False, an error is raised if this is not possible. Otherwise, generated edges form a partial augmentation, which k-edge-connects any part of G where it is possible, and maximally connects the remaining parts.

Raises
NetworkXUnfeasible

If partial is False and no k-edge-augmentation exists.

NetworkXNotImplemented

If the input graph is directed or a multigraph.

ValueError:

If k is less than 1

Notes

When k=1 this returns an optimal solution.

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

For k>3, this problem is NP-hard and this uses a randomized algorithm that

produces a feasible solution, but provides no guarantees on the solution weight.

Examples

```>>> # Unweighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> sorted(nx.k_edge_augmentation(G, k=1))
[(1, 5)]
>>> sorted(nx.k_edge_augmentation(G, k=2))
[(1, 5), (5, 4)]
>>> sorted(nx.k_edge_augmentation(G, k=3))
[(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
>>> complement = list(nx.k_edge_augmentation(G, k=5, partial=True))
>>> nx.edge_connectivity(G)
4
```
```>>> # Weighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> # avail can be a tuple with a dict
>>> avail = [(1, 5, {"weight": 11}), (2, 5, {"weight": 10})]
>>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight="weight"))
[(2, 5)]
>>> # or avail can be a 3-tuple with a real number
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # or avail can be a dict
>>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # If augmentation is infeasible, then a partial solution can be found
>>> avail = {(1, 5): 11}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True))
[(1, 5)]
```