EdgeComponentAuxGraph.construct

classmethod EdgeComponentAuxGraph.construct(G)

Builds an auxiliary graph encoding edge-connectivity between nodes.

Parameters:

GNetworkX graph

Notes

Given G=(V, E), initialize an empty auxiliary graph A. Choose an arbitrary source node s. Initialize a set N of available nodes (that can be used as the sink). The algorithm picks an arbitrary node t from N - {s}, and then computes the minimum st-cut (S, T) with value w. If G is directed the minimum of the st-cut or the ts-cut is used instead. Then, the edge (s, t) is added to the auxiliary graph with weight w. The algorithm is called recursively first using S as the available nodes and s as the source, and then using T and t. Recursion stops when the source is the only available node.