partial_k_edge_augmentation(G, k, avail, weight=None)
When a k-edge-augmentation is not possible, we can still try to find a small set of edges that partially k-edge-connects as much of the graph as possible. All possible edges are generated between remaining parts. This minimizes the number of k-edge-connected subgraphs in the resulting graph and maxmizes the edge connectivity between those subgraphs.
Construct H that augments G with all edges in avail. Find the k-edge-subgraphs of H. For each k-edge-subgraph, if the number of nodes is more than k, then find the k-edge-augmentation of that graph and add it to the solution. Then add all edges in avail between k-edge subgraphs to the solution.
An undirected graph.
Desired edge connectivity
For more details, see k_edge_augmentation
.
key to use to find weights if avail
is a set of 3-tuples. For more details, see k_edge_augmentation
.
Finds augmentation that k-edge-connects as much of the graph as possible.
Edges in the partial augmentation of G. These edges k-edge-connect any part of G where it is possible, and maximally connects the remaining parts. In other words, all edges from avail are generated except for those within subgraphs that have already become k-edge-connected.
k_edge_augmentation
func
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))See :
... G.add_node(8)
... avail = [(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (1, 8)]
... sorted(partial_k_edge_augmentation(G, k=2, avail=avail)) [(1, 5), (1, 8)]
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
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