diff env/lib/python3.9/site-packages/networkx/algorithms/connectivity/utils.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/connectivity/utils.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,85 @@
+"""
+Utilities for connectivity package
+"""
+import networkx as nx
+
+__all__ = ["build_auxiliary_node_connectivity", "build_auxiliary_edge_connectivity"]
+
+
+def build_auxiliary_node_connectivity(G):
+    r"""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
+
+    """
+    directed = G.is_directed()
+
+    mapping = {}
+    H = nx.DiGraph()
+
+    for i, node in enumerate(G):
+        mapping[node] = i
+        H.add_node(f"{i}A", id=node)
+        H.add_node(f"{i}B", id=node)
+        H.add_edge(f"{i}A", f"{i}B", capacity=1)
+
+    edges = []
+    for (source, target) in G.edges():
+        edges.append((f"{mapping[source]}B", f"{mapping[target]}A"))
+        if not directed:
+            edges.append((f"{mapping[target]}B", f"{mapping[source]}A"))
+    H.add_edges_from(edges, capacity=1)
+
+    # Store mapping as graph attribute
+    H.graph["mapping"] = mapping
+    return H
+
+
+def build_auxiliary_edge_connectivity(G):
+    """Auxiliary digraph for computing flow based edge connectivity
+
+    If the input graph is undirected, we replace each edge (`u`,`v`) with
+    two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute
+    'capacity' for each arc to 1. If the input graph is directed we simply
+    add the 'capacity' attribute. Part of algorithm 1 in [1]_ .
+
+    References
+    ----------
+    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. (this is a
+        chapter, look for the reference of the book).
+        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
+    """
+    if G.is_directed():
+        H = nx.DiGraph()
+        H.add_nodes_from(G.nodes())
+        H.add_edges_from(G.edges(), capacity=1)
+        return H
+    else:
+        H = nx.DiGraph()
+        H.add_nodes_from(G.nodes())
+        for (source, target) in G.edges():
+            H.add_edges_from([(source, target), (target, source)], capacity=1)
+        return H