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

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