Skip to main content
`Ctrl`+`K`

# k_edge_augmentation

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

  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 guaranteed 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:
    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))
      >>> 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

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