Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

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 [R227].

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

 [R227] (1, 2) 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