Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.algorithms.connectivity.utils.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 .

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