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
9
10
11
12
13
14
15 try:
16 import numpy as N
17 except:
18 raise ImportError, 'numpy not found'
19
20 import networkx
21
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
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
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
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
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
76 """Return eigenvalues of the Laplacian of G"""
77 return N.linalg.eigvals(laplacian(G))
78
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
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
102 nxbase=sys.path[0]+os.sep+os.pardir
103 sys.path.insert(0,nxbase)
104 unittest.TextTestRunner().run(_test_suite())
105