function [edges x]= get_next_tree(n,y)
% [edges x] = get_next_tree(n)
% [edges x] = get_next_tree(n,y)
% 
% This code is for the enumeration of trees using Prufer sequences.
% 
% INPUT: n = number of nodes in the tree
%        y = previous prufer sequence.
%        If y is left off the arguments, the first prufer sequence is
%        given.
%
% OUTPUT: edges = an n x n matrix with 1s where there are edges in the tree
%                 and 0s where there are none.
%         x = the corresponding prufer sequence. This should be used as 
%             input (y) to get the next tree.
%
% Example: 
%
%     [tree_edges prufer] = get_next_tree(n);
%
%     % Iterate through all unrooted trees
%     for itree = 1:(n^(n-2)-1)
%    
%       % For each unrooted tree, there are n rooted trees.
%       for iroot = 1:n      
%              % Here you do what you want with your tree.
%       end    
%
%    % Enumerate the next tree
%    [tree_edges prufer] = get_next_tree(n,prufer);
%    end

% Laura Balzano, University of Wisconsin-Madison
% September 2008
% sunbeam@ece.wisc.edu


if nargin == 1
    x = ones(1,n-2);
else
    x = get_next_prufer(y,n);
end

edges = decode_prufer(x);

%% --------------------
function edges = decode_prufer(x)

n = length(x)+2;

% Decode prufer sequence
edges = zeros(n);
nodes = 1:n;

for m = 1:n-2

    ni = 1;
    k = nodes(ni);
    flag = 1;
    while(flag)
        if isempty(find(x==k,1))
            ki = find(nodes==k); 
            flag = 0;
        else
            ni = ni+1;
            k=nodes(ni);
        end
    end

    j = x(1);
    edges(k,j)=1;
    edges(j,k)=1;

    x = x(2:end);
    nodes = [nodes(1:ki-1) nodes(ki+1:end)];

end

edges(nodes(1),nodes(2))=1;
edges(nodes(2),nodes(1))=1;
return;

%% --------------------
function s = get_next_prufer(x,n)

j=n-2;
while(j > 1 & x(j)>=n)
    x(j)=1;
    j = j-1;
end
x(j)=x(j)+1;
s = x;
return;