unconstrained_bridge_augmentation(G)
This is an implementation of the algorithm detailed in . The basic idea is to construct a meta-graph of bridge-ccs, connect leaf nodes of the trees to connect the entire graph, and finally connect the leafs of the tree in dfs-preorder to bridge connect the entire graph.
Input: a graph G. First find the bridge components of G and collapse each bridge-cc into a node of a metagraph graph C, which is guaranteed to be a forest of trees.
C contains p "leafs" --- nodes with exactly one incident edge. C contains q "isolated nodes" --- nodes with no incident edges.
Theorem: If p + q > 1, then at least $ceil(p / 2) + q$ edges are
needed to bridge connect C. This algorithm achieves this min number.
The method first adds enough edges to make G into a tree and then pairs leafs in a simple fashion.
Let n be the number of trees in C. Let v(i) be an isolated vertex in the i-th tree if one exists, otherwise it is a pair of distinct leafs nodes in the i-th tree. Alternating edges from these sets (i.e. adding edges A1 = [(v(i)[0], v(i + 1)[1]), v(i + 1)[0], v(i + 2)[1])...]) connects C into a tree T. This tree has p' = p + 2q - 2(n -1) leafs and no isolated vertices. A1 has n - 1 edges. The next step finds ceil(p' / 2) edges to biconnect any tree with p' leafs.
Convert T into an arborescence T' by picking an arbitrary root node with degree >= 2 and directing all edges away from the root. Note the implementation implicitly constructs T'.
The leafs of T are the nodes with no existing edges in T'. Order the leafs of T' by DFS prorder. Then break this list in half and add the zipped pairs to A2.
The set A = A1 + A2 is the minimum augmentation in the metagraph.
To convert this to edges in the original graph
An undirected graph.
Finds an optimal 2-edge-augmentation of G using the fewest edges.
Edges in the bridge augmentation of G
bridge_augmentation
func
k_edge_augmentation
func
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
... sorted(unconstrained_bridge_augmentation(G)) [(1, 7)]
>>> G = nx.path_graph((1, 2, 3, 2, 4, 5, 6, 7))
... sorted(unconstrained_bridge_augmentation(G)) [(1, 3), (3, 7)]
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])See :
... G.add_node(4)
... sorted(unconstrained_bridge_augmentation(G)) [(1, 4), (4, 0)]
The following pages refer to to this document either explicitly or contain code examples using this.
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