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
nodes and
edges we derive a directed graph D with
nodes and
arcs by replacing each original node
with two nodes
,
linked by an (internal) arc in D. Then for each edge (
,
) in G we add two arcs (
,
) and (
,
) in D. Finally we set the attribute capacity = 1 for each arc in D [1].
For a directed graph having
nodes and
arcs we derive a directed graph D with
nodes and
arcs by replacing each original node
with two nodes
,
linked by an (internal) arc (
,
) in D. Then for each arc (
,
) in G we add one arc (
,
) 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