function [argmaxDelta,Delta]=l1o_knng(X,x,k,gamma)

[p,n]=size(X);

X1=[X x];
G=zeros(n+1,n+1);


% k-NNG for the full training + test sample
D=L2_distance(X1,X1); D=D.^2;
for i=1:n+1
    di=D(i,:); [di,knni]=sort(di,'ascend');
    G(i,knni(2:k+1))=D(i,knni(2:k+1)); % build the graph (outgoing edges only, non-symmetric)
    k1(i)=knni(k+2); % keep the k+1st NN for later
end

% L1O k-NNG
% Delta=L*ones(1,n+1);
% for i=1:n+1
%     i
%     Gi=zeros(n,n);
%     Xi=setdiff(X1',X1(:,i)','rows')';
%     Di=L2_distance(Xi,Xi);
%     for j=1:n
%         dj=Di(j,:); [dj,knnj]=sort(dj,'ascend');
%         Gi(j,knnj(2:k+1))=Di(j,knnj(2:k+1)); % build the graph
%     end
%     Li=sum(Gi(:));
%     Delta(i)=Delta(i)-Li;
% end

% L1O k-NNG
Delta=zeros(1,n+1);
for i=1:n+1
    % outgoing + incoming - intersection (aux)
    aux= G(i,:) & G(:,i)';
    Delta(i)=sum(G(i,:).^gamma)+sum(G(:,i).^gamma) -sum(aux.^gamma);
    
    knni=find(G(:,i)); % find the points that had Xi as a NN (incoming edges)   
    m=length(knni);
    for j=1:m % add k+1st NN for those points and subtract the edge weight
        Delta(i)=Delta(i)-D(k1(knni(j)),knni(j)).^gamma;
    end
end

[maxDelta,argmaxDelta]=max(Delta);