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 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.

  • 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

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.

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)]