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 kedgeconnect 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 kedgeconnects G. In general, finding a kedgeaugmentation is NPhard, so solutions are not garuenteed to be minimal. Furthermore, a kedgeaugmentation 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 3tuple
(u, v, d)
or a dict with items(u, v): d
. The third item,d
, can be a dictionary or a real number. Ifd
is a dictionaryd[weight]
correspondings to the weight.weight (string) – key to use to find weights if
avail
is a set of 3tuples where the third item in each tuple is a dictionary.partial (boolean) – If partial is True and no feasible kedgeaugmentation exists, then all a partial kedgeaugmentation is generated. Adding the edges in a partial augmentation to G, minimizes the number of kedgeconnected 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 kedgeconnected. If partial is False, an error is raised if this is not possible. Otherwise, generated edges form a partial augmentation, which kedgeconnects any part of G where it is possible, and maximally connects the remaining parts.
 Raises
NetworkXUnfeasible – If partial is False and no kedgeaugmentation 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 2approximation of the optimal solution. For k>3, this problem is NPhard 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 3tuple 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)]