% p = etree_unbalance(A)
%
% Return an equivalent fill ordering that hopefully unbalances the etree.
% This is an algorithm of Joseph Liu's

function p = etree_unbalance(A)

n = length(A);
t = etree(A);

subtreecount = ones(1,n);
for i = 1:n-1
   if t(i)
      subtreecount(t(i)) = subtreecount(t(i)) + subtreecount(i);
   end
end

I = 1:n;   I(find(t==0)) = [];
J = t;     J(find(t==0)) = [];
S = sparse(I,J,1,n,n);
x = n;
while 1
   children = find(S(:,x));
   if isempty(children)
      break;
   else
      [junk,bestchild] = max(subtreecount(children));
      x = children(bestchild);
   end
end

p = comprotate(A,x);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% p = comprotate (A,x)
%
% Given a symmetric matrix A and the number of one of its
% nodes, do a composite etree rotation to bring x to the root. The new
% ordering is returned in p.
% This is an algorithm of Joseph Liu's

function p = comprotate (A,x)

n = length(A);
t = etree(A);
I = 1:n;   I(find(t==0)) = [];
J = t;     J(find(t==0)) = [];
S = speye(n) - sparse(I,J,1,n,n);    % upper triangular form of etree
p = [];

z = x;
unnumbered = ones(n,1);
while t(z)
   e = zeros(n,1);
   e(z) = 1;
   subtree = S\e;
   adj = any(A(:,find(subtree)),2);
   adj = adj & ~subtree;
   adj(z) = 1;
   adj = adj & unnumbered;
   adj = find(adj);
   p = [p adj'];
   unnumbered(adj) = 0;
   z = t(z);
end

p = [find(unnumbered)' p(end:-1:1)];