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:	G (NetworkX graph) – An undirected graph. k (integer) – Desired edge connectivity avail (dict 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 optinal 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. weight (string) – key to use to find weights if `avail` is a set of 3-tuples where the third item in each tuple is a dictionary. partial (boolean) – 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:	edge (tuple) – 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 gaurentees on the solution weight.

Example

>>> # Unweighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> 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))
>>> G.add_edges_from(complement)
>>> nx.edge_connectivity(G)
4

Example

>>> # Weighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> # 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)]