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

Source Code for Module networkx.utils

  1  """ 
  2  Utilities for networkx package 
  3   
  4  """ 
  5  __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 
  6  __date__ = "$Date: 2005-06-15 08:30:40 -0600 (Wed, 15 Jun 2005) $" 
  7  __credits__ = """""" 
  8  __revision__ = "$Revision: 1029 $" 
  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 random 
 16  import networkx 
 17   
 18  ### some cookbook stuff 
 19   
 20  # used in deciding whether something is a bunch of nodes, edges, etc. 
 21  # see G.add_nodes and others in Graph Class in networkx/base.py 
22 -def is_singleton(obj):
23 """ Is string_like or not iterable. """ 24 return hasattr(obj,"capitalize") or not hasattr(obj,"__iter__")
25
26 -def is_string_like(obj): # from John Hunter, types-free version
27 """Check if obj is string.""" 28 # if hasattr(obj, 'shape'): return False # this is a workaround 29 # for a bug in numeric<23.1 30 try: 31 obj + '' 32 except (TypeError, ValueError): 33 return False 34 return True 35 36
37 -def iterable(obj):
38 """ Return True if obj is iterable with a well-defined len() """ 39 if hasattr(obj,"__iter__"): return True 40 try: 41 len(obj) 42 except: 43 return False 44 return True
45
46 -def flatten(obj, result=None):
47 """ Return flattened version of (possibly nested) iterable obj. """ 48 if not iterable(obj) or is_string_like(obj): 49 return obj 50 if result is None: 51 result = [] 52 for item in obj: 53 if not iterable(item) or is_string_like(item): 54 result.append(item) 55 else: 56 flatten(item, result) 57 return obj.__class__(result)
58
59 -def iterable_to_string(obj, sep=''):
60 """ 61 Return string obtained by concatenating the string representation 62 of each element of an iterable obj, with an optional internal string 63 separator specified. 64 """ 65 if not iterable(obj): 66 return str(obj) 67 return sep.join([str(i) for i in obj])
68
69 -def is_list_of_ints( intlist ):
70 """ Return True if list is a list of ints. """ 71 if not isinstance(intlist,list): return False 72 for i in intlist: 73 if not isinstance(i,int): return False 74 return True
75
76 -def _get_fh(path, mode='r'):
77 """ Return a file handle for given path. 78 79 Path can be a string or a file handle. 80 81 Attempt to uncompress/compress files ending in '.gz' and '.bz2'. 82 83 """ 84 if is_string_like(path): 85 if path.endswith('.gz'): 86 import gzip 87 fh = gzip.open(path,mode=mode) 88 elif path.endswith('.bz2'): 89 import bz2 90 fh = bz2.BZ2File(path,mode=mode) 91 else: 92 fh = file(path,mode=mode) 93 elif hasattr(path, 'seek'): 94 fh = path 95 else: 96 raise ValueError('path must be a string or file handle') 97 return fh
98 99 100 ##def iterable(obj): 101 ## """ Return True if obj is iterable with a well-defined len()""" 102 ## try: 103 ## len(obj) 104 ## except: 105 ## return False 106 ## else: 107 ## return True 108 109 110 # some helpers for choosing random sequences from distributions 111 # uses scipy: www.scipy.org 112
113 -def scipy_pareto_sequence(n,exponent=1.0):
114 """ 115 Return sample sequence of length n from a Pareto distribution. 116 117 """ 118 try: 119 import scipy.stats as stats 120 except ImportError: 121 print "Import error: not able to import scipy" 122 return 123 random._inst = random.Random() 124 stats.seed(random.randint(1,2**30),random.randint(1,2**30)) 125 return stats.pareto(exponent,size=n)
126 127
128 -def scipy_powerlaw_sequence(n,exponent=2.0):
129 """ 130 Return sample sequence of length n from a power law distribution. 131 132 """ 133 try: 134 import scipy.stats as stats 135 except ImportError: 136 print "Import error: not able to import scipy" 137 return 138 random._inst = random.Random() 139 stats.seed(random.randint(1,2**30),random.randint(1,2**30)) 140 return stats.pareto(exponent-1,size=n)
141 142
143 -def scipy_poisson_sequence(n,mu=1.0):
144 """ 145 Return sample sequence of length n from a Poisson distribution. 146 147 """ 148 try: 149 import scipy.stats as stats 150 except ImportError: 151 print "Import error: not able to import scipy" 152 return 153 random._inst = random.Random() 154 stats.seed(random.randint(1,2**30),random.randint(1,2**30)) 155 return stats.poisson(mu,size=n)
156
157 -def scipy_uniform_sequence(n):
158 """ 159 Return sample sequence of length n from a uniform distribution. 160 161 """ 162 try: 163 import scipy.stats as stats 164 except ImportError: 165 print "Import error: not able to import scipy" 166 return 167 random._inst = random.Random() 168 stats.seed(random.randint(1,2**30),random.randint(1,2**30)) 169 return stats.uniform(size=n)
170
171 -def scipy_discrete_sequence(n,distribution=False):
172 """ 173 Return sample sequence of length n from a given discrete distribution 174 175 distribution=histogram of values, will be normalized 176 177 """ 178 try: 179 import scipy.stats as stats 180 except ImportError: 181 print "Import error: not able to import scipy" 182 return 183 import bisect 184 if not distribution: 185 return "no distribution specified" 186 p=distribution 187 random._inst = random.Random() 188 189 # make CDF out of distribution to use for sample 190 cdf=[] 191 cdf.append(0.0) 192 psum=float(sum(p)) 193 for i in range(0,len(p)): 194 cdf.append(cdf[i]+p[i]/psum) 195 196 # get a uniform random number 197 stats.seed(random.randint(1,2**30),random.randint(1,2**30)) 198 inputseq=stats.uniform(size=n) 199 200 # choose from CDF 201 seq=[bisect.bisect_left(cdf,s)-1 for s in inputseq] 202 return seq
203 204 205 # some helpers for choosing random sequences from distributions 206 # uses pygsl: pygsl.sourceforge.org, but not all its functionality. 207 # note: gsl's default number generator is the same as Python's 208 # (Mersenne Twister) 209
210 -def gsl_pareto_sequence(n,exponent=1.0,scale=1.0,seed=None):
211 """ 212 Return sample sequence of length n from a Pareto distribution. 213 214 """ 215 try: 216 import pygsl.rng 217 except ImportError: 218 print "Import error: not able to import pygsl" 219 return 220 rng=pygsl.rng.rng() 221 random._inst = random.Random() 222 if seed is None: 223 seed=random.randint(1,2**32-1) 224 rng.set(seed) 225 226 return rng.pareto(exponent,scale,n)
227
228 -def gsl_powerlaw_sequence(n,exponent=2.0,scale=1.0,seed=None):
229 """ 230 Return sample sequence of length n from a power law distribution. 231 232 """ 233 try: 234 import pygsl.rng 235 except ImportError: 236 print "Import error: not able to import pygsl" 237 return 238 rng=pygsl.rng.rng() 239 random._inst = random.Random() 240 if seed is None: 241 seed=random.randint(1,2**32-1) 242 rng.set(seed) 243 244 return rng.pareto(exponent-1,scale,n)
245
246 -def gsl_poisson_sequence(n,mu=1.0,seed=None):
247 """ 248 Return sample sequence of length n from a Poisson distribution. 249 250 """ 251 try: 252 import pygsl.rng 253 except ImportError: 254 print "Import error: not able to import pygsl" 255 return 256 rng=pygsl.rng.rng() 257 random._inst = random.Random() 258 if seed is None: 259 seed=random.randint(1,2**32-1) 260 rng.set(seed) 261 262 return rng.poisson(mu,n)
263
264 -def gsl_uniform_sequence(n,seed=None):
265 """ 266 Return sample sequence of length n from a uniform distribution. 267 268 """ 269 try: 270 import pygsl.rng 271 except ImportError: 272 print "Import error: not able to import pygsl" 273 return 274 rng=pygsl.rng.rng() 275 random._inst = random.Random() 276 if seed is None: 277 seed=random.randint(1,2**32-1) 278 rng.set(seed) 279 280 return rng.uniform(n)
281 282 283 # The same helpers for choosing random sequences from distributions 284 # uses Python's random module 285 # http://www.python.org/doc/current/lib/module-random.html 286
287 -def pareto_sequence(n,exponent=1.0):
288 """ 289 Return sample sequence of length n from a Pareto distribution. 290 """ 291 return [random.paretovariate(exponent) for i in xrange(n)]
292 293
294 -def powerlaw_sequence(n,exponent=2.0):
295 """ 296 Return sample sequence of length n from a power law distribution. 297 """ 298 return [random.paretovariate(exponent-1) for i in xrange(n)]
299 300
301 -def uniform_sequence(n):
302 """ 303 Return sample sequence of length n from a uniform distribution. 304 """ 305 return [ random.uniform(0,n) for i in xrange(n)]
306 307
308 -def cumulative_distribution(distribution):
309 """Return normalized cumulative distribution from discrete distribution.""" 310 311 cdf=[] 312 cdf.append(0.0) 313 psum=float(sum(distribution)) 314 for i in range(0,len(distribution)): 315 cdf.append(cdf[i]+distribution[i]/psum) 316 return cdf
317 318
319 -def discrete_sequence(n, distribution=None, cdistribution=None):
320 """ 321 Return sample sequence of length n from a given discrete distribution 322 or discrete cumulative distribution. 323 324 One of the following must be specified. 325 326 distribution = histogram of values, will be normalized 327 328 cdistribution = normalized discrete cumulative distribution 329 330 """ 331 import bisect 332 333 if cdistribution is not None: 334 cdf=cdistribution 335 elif distribution is not None: 336 cdf=cumulative_distribution(distribution) 337 else: 338 raise networkx.NetworkXError, \ 339 "discrete_sequence: distribution or cdistribution missing" 340 341 342 # get a uniform random number 343 inputseq=[random.random() for i in xrange(n)] 344 345 # choose from CDF 346 seq=[bisect.bisect_left(cdf,s)-1 for s in inputseq] 347 return seq
348
349 -def _test_suite():
350 import doctest 351 suite = doctest.DocFileSuite('tests/utils.txt',package='networkx') 352 return suite
353 354 if __name__ == "__main__": 355 import os 356 import sys 357 import unittest 358 if sys.version_info[:2] < (2, 4): 359 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 360 sys.exit(-1) 361 # directory of networkx package (relative to this) 362 nxbase=sys.path[0]+os.sep+os.pardir 363 sys.path.insert(0,nxbase) # prepend to search path 364 unittest.TextTestRunner().run(_test_suite()) 365