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 andm
edges we derive a directed graph D with2n
nodes and2m+n
arcs by replacing each original nodev
with two nodesvA
,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 andm
arcs we derive a directed graph D with2n
nodes andm+n
arcs by replacing each original nodev
with two nodesvA
,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