function [st,sumwt,edgein,perm] = sparsecut(a,v)
% function [st,sumwt,edgein,perm] = sparsecut(a,v)
% 
% given an adj matrix a,
% and a vector v,
%
% order a by v,
% and return as a set the sparsest cut found.

[vp,perm] = sort(v);
ap = a(perm,perm);

n = length(a);

sumwt = zeros(1,n);
edgein = zeros(1,n);

apu = triu(ap);

sumwt(1) = sum(ap(1,:));
for i = 2:n,
  sumwt(i) = sumwt(i-1) + sum(ap(:,i));
end

edgein = zeros(1,n);
for i = 2:n,
  edgein(i) = edgein(i-1) + sum(apu(:,i));
end

nh = n-2;

[val,ind] = min((sumwt(1:nh)-2*edgein(1:nh)) ./ (sumwt(1:nh) .* ...
						 (sumwt(end)-sumwt(1:nh))));

st = find(v <= vp(ind));