function p = mindeg(A)
% function p = mindeg(A)
% Function that takes a symmetric sparse matrix A, and finds a
% reordering such that (PAP') results in the least fill-in possible
% when performing cholesky's factorization.

A = (abs(A)>0);
[m,n] = size(A);

% initialize degree for each node
p = zeros(m,1); % ordered vector
deg = zeros(m,1);
index = (1:m)';

% find the adjacency set for each node
for k = 1:m
  deg(k) = sum(abs(A(k,:))>0) - 1;
end  

% begin search
for j = 1:m
  [Y,I] = sort(deg);
  K = I(1);
  p(j) = index(K);
  v = [find(A(K,1:K-1)) K+find(A(K,K+1:end))];
  [mv,nv] = size(v);
  for k = 1:nv
    A(v(k),:) = A(v(k),:) + A(K,:);
    deg(v(k)) = sum(abs(A(v(k),:)>0))-2;
  end  
  A = [A(1:K-1,1:K-1) A(1:K-1,K+1:end);...
       A(K+1:end,1:K-1) A(K+1:end,K+1:end)];
  index = [index(1:K-1); index(K+1:end)];
  deg = [deg(1:K-1); deg(K+1:end)];
end