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