function [G,m,M,r,inner_names] = RTLGRAPH(alpha,S,naming)
% RTLGRAPH Generates a graph corresponding to the sequence S
%
% [G,m,M,r] = RTLGRAPH(alpha,S) successively adds edges that split the
% mode names in alpha according to the sequence S.
%
% alpha must be a cell array containing mode names
% 'alpha_1',...,'alpha_N' for some N.
%
% The entries of S must be pairwise distinct and meet a hierarchy
% condition.
%
% G is the graph (Matlab formatting) corresponding to the sequence S with
% nodes 1,...,k with k = length(S)+1.
%
% m is a cell, where m{i} contains the mode names associated to node
% number i.
%
% M is a cell, where M{i} contains all outer mode names alpha_i
% accumulated in branch_r(i). Thereby M{i+1} = S{i} and M{1} = alpha.
%
% r = 1 is the root node.
%
% Examples:
% alpha = mna('alpha',[1,2,3,4]);
% S = binary_tree(alpha);
% [G,m,M,r] = RTLGRAPH(alpha,S)
%
% graph_view(G,m);
% M{2} % returns {'alpha_1','alpha_2'}
% m{2} % returns {'beta_1_2','beta_1','beta_2'}
%
% See also: TENSOR_NODE_NOTATION7_PLAIN_NETWORKS, GRAPH, VIEW,
% BINARY_TREE, LINEAR_TREE, RANDOM_TREE, DERIVE_M

k = length(S)+1;

if nargin <= 2
naming = [];
else
inner_names = mna(naming,1:k-1);
end

G = graph; G = addnode(G,1);
m = cell(1,k);
m{1} = alpha;
r = 1;

M = cell(1,k-1);
M{1} = alpha;

for i = 1:k-1
b = find_sub_leaf(G,M,S{i},1,[]);
if isempty(naming)
beta_name = alpha_to_beta(S{i}); % form name for edge
else
beta_name = inner_names{i};
end

G = addedge(G,b,i+1);
m{b} = listdiff([m{b},beta_name],S{i}); % why listdiff?
m{i+1} = [beta_name,S{i}];
M{i+1} = S{i};

% view(G,m);
end

end

function u = find_sub_leaf(G,M,S,h1,P)

branch = int_setdiff(neighbors(G,h1),P);
if isempty(branch)
u = h1;
return;
end

for h2 = branch
if all(ismember(S,M{h2}))
u = find_sub_leaf(G,M,S,h2,h1);
return
end
end

u = h1;

end

function name = alpha_to_beta(S)
name = 'beta';
nr = zeros(1,length(S));
for i = 1:length(S)
nr(i) = str2num(strrep(S{i},'alpha_',''));
end
nr = sort(nr,'ascend');
name = [name,num2str(nr,'_%d')];
end