k_edge_augmentation(G, k, avail=None, weight=None, partial=False)
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.
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.
An undirected graph.
Desired edge connectivity
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.
key to use to find weights if avail
is a set of 3-tuples where the third item in each tuple is a dictionary.
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
.
If partial is False and no k-edge-augmentation exists.
If the input graph is directed or a multigraph.
If k is less than 1
Finds set of edges to k-edge-connect G.
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.
>>> # 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 foundSee :
... avail = {(1, 5): 11}
... sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True)) [(1, 5)]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.connectivity.edge_augmentation.partial_k_edge_augmentation
networkx.algorithms.connectivity.edge_augmentation.weighted_bridge_augmentation
networkx.algorithms.connectivity.edge_augmentation.one_edge_augmentation
networkx.algorithms.connectivity.edge_augmentation.weighted_one_edge_augmentation
networkx.algorithms.connectivity.edge_augmentation.k_edge_augmentation
networkx.algorithms.connectivity.edge_augmentation.bridge_augmentation
networkx.algorithms.connectivity.edge_augmentation.unconstrained_one_edge_augmentation
networkx.algorithms.connectivity.edge_augmentation.unconstrained_bridge_augmentation
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them