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)"""
#    Copyright (C) 2004-2015 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

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