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