diff env/lib/python3.9/site-packages/networkx/algorithms/hybrid.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/hybrid.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,192 @@
+"""
+Provides functions for finding and testing for locally `(k, l)`-connected
+graphs.
+
+"""
+import copy
+import networkx as nx
+
+__all__ = ["kl_connected_subgraph", "is_kl_connected"]
+
+
+def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False):
+    """Returns the maximum locally `(k, l)`-connected subgraph of `G`.
+
+    A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
+    graph there are at least `l` edge-disjoint paths of length at most `k`
+    joining `u` to `v`.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        The graph in which to find a maximum locally `(k, l)`-connected
+        subgraph.
+
+    k : integer
+        The maximum length of paths to consider. A higher number means a looser
+        connectivity requirement.
+
+    l : integer
+        The number of edge-disjoint paths. A higher number means a stricter
+        connectivity requirement.
+
+    low_memory : bool
+        If this is True, this function uses an algorithm that uses slightly
+        more time but less memory.
+
+    same_as_graph : bool
+        If True then return a tuple of the form `(H, is_same)`,
+        where `H` is the maximum locally `(k, l)`-connected subgraph and
+        `is_same` is a Boolean representing whether `G` is locally `(k,
+        l)`-connected (and hence, whether `H` is simply a copy of the input
+        graph `G`).
+
+    Returns
+    -------
+    NetworkX graph or two-tuple
+        If `same_as_graph` is True, then this function returns a
+        two-tuple as described above. Otherwise, it returns only the maximum
+        locally `(k, l)`-connected subgraph.
+
+    See also
+    --------
+    is_kl_connected
+
+    References
+    ----------
+    .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
+            Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
+            2004. 89--104.
+
+    """
+    H = copy.deepcopy(G)  # subgraph we construct by removing from G
+
+    graphOK = True
+    deleted_some = True  # hack to start off the while loop
+    while deleted_some:
+        deleted_some = False
+        # We use `for edge in list(H.edges()):` instead of
+        # `for edge in H.edges():` because we edit the graph `H` in
+        # the loop. Hence using an iterator will result in
+        # `RuntimeError: dictionary changed size during iteration`
+        for edge in list(H.edges()):
+            (u, v) = edge
+            # Get copy of graph needed for this search
+            if low_memory:
+                verts = {u, v}
+                for i in range(k):
+                    for w in verts.copy():
+                        verts.update(G[w])
+                G2 = G.subgraph(verts).copy()
+            else:
+                G2 = copy.deepcopy(G)
+            ###
+            path = [u, v]
+            cnt = 0
+            accept = 0
+            while path:
+                cnt += 1  # Found a path
+                if cnt >= l:
+                    accept = 1
+                    break
+                # record edges along this graph
+                prev = u
+                for w in path:
+                    if prev != w:
+                        G2.remove_edge(prev, w)
+                        prev = w
+                #                path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
+                try:
+                    path = nx.shortest_path(G2, u, v)  # ??? should "Cutoff" be k+1?
+                except nx.NetworkXNoPath:
+                    path = False
+            # No Other Paths
+            if accept == 0:
+                H.remove_edge(u, v)
+                deleted_some = True
+                if graphOK:
+                    graphOK = False
+    # We looked through all edges and removed none of them.
+    # So, H is the maximal (k,l)-connected subgraph of G
+    if same_as_graph:
+        return (H, graphOK)
+    return H
+
+
+def is_kl_connected(G, k, l, low_memory=False):
+    """Returns True if and only if `G` is locally `(k, l)`-connected.
+
+    A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
+    graph there are at least `l` edge-disjoint paths of length at most `k`
+    joining `u` to `v`.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        The graph to test for local `(k, l)`-connectedness.
+
+    k : integer
+        The maximum length of paths to consider. A higher number means a looser
+        connectivity requirement.
+
+    l : integer
+        The number of edge-disjoint paths. A higher number means a stricter
+        connectivity requirement.
+
+    low_memory : bool
+        If this is True, this function uses an algorithm that uses slightly
+        more time but less memory.
+
+    Returns
+    -------
+    bool
+        Whether the graph is locally `(k, l)`-connected subgraph.
+
+    See also
+    --------
+    kl_connected_subgraph
+
+    References
+    ----------
+    .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
+            Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
+            2004. 89--104.
+
+    """
+    graphOK = True
+    for edge in G.edges():
+        (u, v) = edge
+        # Get copy of graph needed for this search
+        if low_memory:
+            verts = {u, v}
+            for i in range(k):
+                [verts.update(G.neighbors(w)) for w in verts.copy()]
+            G2 = G.subgraph(verts)
+        else:
+            G2 = copy.deepcopy(G)
+        ###
+        path = [u, v]
+        cnt = 0
+        accept = 0
+        while path:
+            cnt += 1  # Found a path
+            if cnt >= l:
+                accept = 1
+                break
+            # record edges along this graph
+            prev = u
+            for w in path:
+                if w != prev:
+                    G2.remove_edge(prev, w)
+                    prev = w
+            #            path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
+            try:
+                path = nx.shortest_path(G2, u, v)  # ??? should "Cutoff" be k+1?
+            except nx.NetworkXNoPath:
+                path = False
+        # No Other Paths
+        if accept == 0:
+            graphOK = False
+            break
+    # return status
+    return graphOK