Source Code for Module networkx.spectrum

  1  """ 
  2  Laplacian, adjacency matrix, and spectrum of graphs. 
  3   
  4  Needs numpy array package: numpy.scipy.org. 
  5   
  6  """ 
  7  __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 
  8  #    Copyright (C) 2004-2006 by  
  9  #    Aric Hagberg <hagberg@lanl.gov> 
 10  #    Dan Schult <dschult@colgate.edu> 
 11  #    Pieter Swart <swart@lanl.gov> 
 12  #    Distributed under the terms of the GNU Lesser General Public License 
 13  #    http://www.gnu.org/copyleft/lesser.html 
 14   
 15  try: 
 16      import numpy as N 
 17  except: 
 18      raise ImportError, 'numpy not found' 
 19   
 20  import networkx 
 21   
 22 -def adj_matrix(G,nodelist=None): 
 23      """Return adjacency matrix of graph as a numpy matrix. 
 24   
 25      This just calls networkx.convert.to_numpy_matrix. 
 26   
 27      If you want a pure python adjacency matrix represntation try 
 28      networkx.convert.to_dict_of_dicts with weighted=False, 
 29      which will return a dictionary-of-dictionaries format that 
 30      can be addressed as a sparse matrix. 
 31   
 32      """ 
 33      return networkx.to_numpy_matrix(G,nodelist=nodelist) 
 34   
 35   
 36 -def laplacian(G,nodelist=None): 
 37      """Return standard combinatorial Laplacian of G as a numpy matrix. 
 38   
 39      Return the matrix L = D - A, where 
 40   
 41         D is the diagonal matrix in which the i'th entry is the degree of node i 
 42         A is the adjacency matrix. 
 43   
 44      """ 
 45      # this isn't the most efficient way to do this... 
 46      n=G.order() 
 47      I=N.identity(n) 
 48      A=N.asarray(networkx.to_numpy_matrix(G,nodelist=nodelist)) 
 49      D=I*N.sum(A,axis=1) 
 50      L=D-A 
 51      return L 
 52   
 53   
 54 -def normalized_laplacian(G,nodelist=None): 
 55      """Return normalized Laplacian of G as a numpy matrix. 
 56   
 57      See Spectral Graph Theory by Fan Chung-Graham. 
 58      CBMS Regional Conference Series in Mathematics, Number 92, 
 59      1997. 
 60   
 61      """ 
 62      # FIXME: this isn't the most efficient way to do this... 
 63      n=G.order() 
 64      I=N.identity(n) 
 65      A=N.asarray(networkx.to_numpy_matrix(G,nodelist=nodelist)) 
 66      d=N.sum(A,axis=1) 
 67      L=I*d-A 
 68      osd=N.zeros(len(d)) 
 69      for i in range(len(d)): 
 70          if d[i]>0: osd[i]=N.sqrt(1.0/d[i]) 
 71      T=I*osd 
 72      L=N.dot(T,N.dot(L,T)) 
 73      return L 
 74   
 75 -def laplacian_spectrum(G): 
 76      """Return eigenvalues of the Laplacian of G"""  
 77      return N.linalg.eigvals(laplacian(G)) 
 78   
 79 -def adjacency_spectrum(G): 
 80      """Return eigenvalues of the adjacency matrix of G"""  
 81      return N.linalg.eigvals(adj_matrix(G)) 
 82   
 83   
 84  combinatorial_laplacian=laplacian 
 85  generalized_laplacian=normalized_laplacian 
 86   
 87   
 88 -def _test_suite(): 
 89      import doctest 
 90      suite = doctest.DocFileSuite('tests/spectrum.txt',package='networkx') 
 91      return suite 
 92   
 93   
 94  if __name__ == "__main__": 
 95      import os 
 96      import sys 
 97      import unittest 
 98      if sys.version_info[:2] < (2, 4): 
 99          print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2] 
100          sys.exit(-1) 
101      # directory of networkx package (relative to this) 
102      nxbase=sys.path[0]+os.sep+os.pardir 
103      sys.path.insert(0,nxbase) # prepend to search path 
104      unittest.TextTestRunner().run(_test_suite()) 
105