aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py
diff options
context:
space:
mode:
authorS. Solomon Darnell2025-03-28 21:52:21 -0500
committerS. Solomon Darnell2025-03-28 21:52:21 -0500
commit4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch)
treeee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py
parentcc961e04ba734dd72309fb548a2f97d67d578813 (diff)
downloadgn-ai-master.tar.gz
two version of R2R are hereHEADmaster
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py196
1 files changed, 196 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py
new file mode 100644
index 00000000..9d3dd307
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/hybrid.py
@@ -0,0 +1,196 @@
+"""
+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"]
+
+
+@nx._dispatchable(returns_graph=True)
+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
+
+
+@nx._dispatchable
+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