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, Springer-Verlag, 2005. http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf