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 guaranteed 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. Ifd
is a dictionaryd[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)) >>> 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)]