Package networkx :: Module hybrid
[hide private]
[frames] | no frames]

Source Code for Module networkx.hybrid

  1  """ 
  2  Hybrid  
  3   
  4  """ 
  5  __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult (dschult@colgate.edu)""" 
  6  __date__ = "$Date: 2005-03-30 16:56:28 -0700 (Wed, 30 Mar 2005) $" 
  7  __credits__ = """""" 
  8  __revision__ = "$Revision: 911 $" 
  9  #    Copyright (C) 2004,2005 by  
 10  #    Aric Hagberg <hagberg@lanl.gov> 
 11  #    Dan Schult <dschult@colgate.edu> 
 12  #    Pieter Swart <swart@lanl.gov> 
 13  #    Distributed under the terms of the GNU Lesser General Public License 
 14  #    http://www.gnu.org/copyleft/lesser.html 
 15  import copy 
 16  import sets 
 17  from networkx.path import shortest_path 
 18   
19 -def kl_connected_subgraph(G,k,l,low_memory=False,same_as_graph=False):
20 """ Returns the maximum locally (k,l) connected subgraph of G. 21 22 (k,l)-connected subgraphs are presented by Fan Chung and Li 23 in "The Small World Phenomenon in hybrid power law graphs" 24 to appear in "Complex Networks" (Ed. E. Ben-Naim) Lecture 25 Notes in Physics, Springer (2004) 26 27 low_memory=True then use a slightly slower, but lower memory version 28 same_as_graph=True then return a tuple with subgraph and 29 pflag for if G is kl-connected 30 """ 31 H=copy.deepcopy(G) # subgraph we construct by removing from G 32 33 graphOK=True 34 deleted_some=True # hack to start off the while loop 35 while deleted_some: 36 deleted_some=False 37 for edge in H.edges(): 38 (u,v)=edge 39 ### Get copy of graph needed for this search 40 if low_memory: 41 verts=sets.Set([u,v]) 42 for i in range(k): 43 [verts.update(G.neighbors(w)) for w in verts.copy()] 44 G2=G.subgraph(list(verts)) 45 else: 46 G2=copy.deepcopy(G) 47 ### 48 path=[u,v] 49 cnt=0 50 accept=0 51 while path: 52 cnt += 1 # Found a path 53 if cnt>=l: 54 accept=1 55 break 56 # record edges along this graph 57 prev=u 58 for w in path: 59 G2.delete_edge(prev,w) 60 prev=w 61 # path=shortest_path(G2,u,v,k) # ??? should "Cutoff" be k+1? 62 path=shortest_path(G2,u,v) # ??? should "Cutoff" be k+1? 63 # No Other Paths 64 if accept==0: 65 H.delete_edge(u,v) 66 deleted_some=True 67 if graphOK: graphOK=False 68 # We looked through all edges and removed none of them. 69 # So, H is the maximal (k,l)-connected subgraph of G 70 if same_as_graph: 71 return (H,graphOK) 72 return H
73
74 -def is_kl_connected(G,k,l,low_memory=False):
75 """Returns True if G is kl connected """ 76 graphOK=True 77 for edge in G.edges(): 78 (u,v)=edge 79 ### Get copy of graph needed for this search 80 if low_memory: 81 verts=sets.Set([u,v]) 82 for i in range(k): 83 [verts.update(G.neighbors(w)) for w in verts.copy()] 84 G2=G.subgraph(list(verts)) 85 else: 86 G2=copy.deepcopy(G) 87 ### 88 path=[u,v] 89 cnt=0 90 accept=0 91 while path: 92 cnt += 1 # Found a path 93 if cnt>=l: 94 accept=1 95 break 96 # record edges along this graph 97 prev=u 98 for w in path: 99 G2.delete_edge(prev,w) 100 prev=w 101 # path=shortest_path(G2,u,v,k) # ??? should "Cutoff" be k+1? 102 path=shortest_path(G2,u,v) # ??? should "Cutoff" be k+1? 103 # No Other Paths 104 if accept==0: 105 graphOK=False 106 break 107 # return status 108 return graphOK
109 110
111 -def _test_suite():
112 import doctest 113 suite = doctest.DocFileSuite('tests/hybrid.txt',package='networkx') 114 return suite
115 116 117 if __name__ == "__main__": 118 import os 119 import sys 120 import unittest 121 if sys.version_info[:2] < (2, 4): 122 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 123 sys.exit(-1) 124 # directory of networkx package (relative to this) 125 nxbase=sys.path[0]+os.sep+os.pardir 126 sys.path.insert(0,nxbase) # prepend to search path 127 unittest.TextTestRunner().run(_test_suite()) 128