# this pseudo code is based on following URL.
# http://neuroimaging.scipy.org/svn/ni/fff/trunk/python/NLDR.py

def LPP(G,X,dim,verbose=0,maxiter=1000):
        """
        Compute the Locality preserving projector of the data
        proj = LPP(G,X,dim,verbose=0,maxiter=1000)
        INPUT:
        - G : Weighted graph that represents the data
        - X : related input dataset
        - dim=1 : number of dimensions
        - verbose = 0: verbosity level
        - maxiter=1000: maximum number of iterations of the algorithm
        OUTPUT
        -proj, array of shape(X.shape[1],dim)
        """
        n = G.V
        dim = N.min(dim,n)
        G = FG.WeightedGraph(G.V,G.edges,G.weights)
        W = G.adjacency()
        D = N.diag(N.sum(W,1))
        M1 = N.dot(N.dot(N.transpose(X),D-W),X)
        M2 = N.dot(N.dot(N.transpose(X),D),X)
        C = L.cholesky(M2)
        iC = L.pinv(C)
        M1 = N.dot(iC,N.dot(M1,N.transpose(iC)))
        M2 = N.dot(iC,N.dot(M2,N.transpose(iC)))


        U,S,V = L.svd(M1,0)
        if verbose:
                print S

        proj = N.dot(N.transpose(iC),U)
        proj = N.vstack([proj[:,-1-i] for i in range(dim)])
        proj = N.transpose(proj)
        proj = proj/N.sqrt(N.sum(proj**2,0))

        return proj

class knn_LPP(NLDR):
        """
        This is a particular class that perfoms linear dimension reduction
        using k nearest neighbor modelling and locality preserving projection (LPP).
        it contains the following ones:
        - k : number of neighbors in the knn graph building
        - G : resulting graph based on the training data
        - embedding: array of shape (nbitems,rdim)
        this is representation of the training data
        - projector: array of shape(fdim,rdim)
        linear part of the embedding
        """
        def test(self,X):
                """
                chart = knn_LPP.test(X,verbose=0)
                INPUT
                X = array of shape(nbitems,fdim)
                new data points to be embedded
                verbose=0 : verbosity mode
                OUTPUT
                chart: resulting rdim-dimensional represntation
                """
                if self.trained ==0:
                        raise ValueError, "Untrained function -- cannot generalize"
                if N.size(X)==self.fdim:
                        X = N.reshape(X,(1,self.fdim))
                self.check_data(X)
                #
                u = N.dot(X,self.projector)
                return u



