### view env/lib/python3.9/site-packages/networkx/algorithms/hybrid.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
"""
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.

--------
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.

--------
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
```