#copyright Igor Rivin, 2003, all rights reserved.
#
#produce the Laplacian matrix of  a graph (as generated by gengraph),
#and then find its eigenvalues. I wrote the C version of this code
#(and the code in gengraph.py) in 1996, and the results obtained were
#the basis of the paper of D. Jakobson, S.J.Miller, Z.Rudnick and
#myself.

import gengraph
from numarray import *
import numarray.linear_algebra as la

def makeadjacency(size, deg, elist):
    newmat = zeros((size, size), type = Float64)
    for i in xrange(size):
        #double below to make sure that the matrix is positive definite,
        #and has condition number no greater than 3
        newmat[i, i] =  deg * 2
        for i in elist:
            newmat[i[0], i[1]] = newmat[i[1], i[0]] = -1
    print newmat
    return newmat

def spectrum(size, deg, elist):
    eigenarray = la.Heigenvalues(makeadjacency(size, deg, elist))
    return eigenarray.tolist()

def doit(size, deg):
    elist = gengraph.makegen(size, deg)
    return [x-deg for x in spectrum(size, deg,  elist)]