networkx 2.8.2 Pypi GitHub Homepage
Other Docs
NotesParametersYieldsBackRef
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.

Notes

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.

Parameters

G : NetworkX graph

An undirected graph.

k : integer

Desired edge connectivity

avail : dict or a set of 2 or 3 tuples

For more details, see k_edge_augmentation .

weight : string

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.

Yields

edge : tuple

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.

See Also

k_edge_augmentation

func

Examples

>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
... 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)]
See :

Back References

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

Local connectivity graph

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


GitHub : /networkx/algorithms/connectivity/edge_augmentation.py#283
type: <class 'function'>
Commit: