build_auxiliary_node_connectivity¶

build_auxiliary_node_connectivity
(G)[source]¶ Creates a directed graph D from an undirected graph G to compute flow based node connectivity.
For an undirected graph G having \(n\) nodes and \(m\) edges we derive a directed graph D with \(2n\) nodes and \(2m+n\) arcs by replacing each original node \(v\) with two nodes \(vA\), \(vB\) linked by an (internal) arc in D. Then for each edge (\(u\), \(v\)) in G we add two arcs (\(uB\), \(vA\)) and (\(vB\), \(uA\)) in D. Finally we set the attribute capacity = 1 for each arc in D [1].
For a directed graph having \(n\) nodes and \(m\) arcs we derive a directed graph D with \(2n\) nodes and \(m+n\) arcs by replacing each original node \(v\) with two nodes \(vA\), \(vB\) linked by an (internal) arc (\(vA\), \(vB\)) in D. Then for each arc (\(u\), \(v\)) in G we add one arc (\(uB\), \(vA\)) in D. Finally we set the attribute capacity = 1 for each arc in D.
A dictionary with a mapping between nodes in the original graph and the auxiliary digraph is stored as a graph attribute: H.graph[‘mapping’].
References
[1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and Erlebach, ‘Network Analysis: Methodological Foundations’, Lecture Notes in Computer Science, Volume 3418, SpringerVerlag, 2005. http://www.informatik.uniaugsburg.de/thi/personen/kammer/Graph_Connectivity.pdf