Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.hybrid

# coding: utf-8
"""
Provides functions for finding and testing for locally (k, l)-connected
graphs.

"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>

_all__ = ['kl_connected_subgraph', 'is_kl_connected']

import copy
import networkx as nx

[docs]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 this is 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
----------
.. : 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
for edge in H.edges():
(u,v)=edge
### Get copy of graph needed for this search
if low_memory:
verts=set([u,v])
for i in range(k):
[verts.update(G.neighbors(w)) for w in verts.copy()]
G2=G.subgraph(list(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 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

[docs]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
----------
.. : 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=set([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