function [type] = tjsr_makecandidate(M, type);
% type = tjsr_makecandidate(M, type);
% This function belongs to tjsr!
%sets the values type 
%   .ordering, .v0, .v0s, 
%   .numcandidate, .numnearlycandidate, .numextravertex, .numordering, 
%   .smpflag 
%
% if v0 is given, then it is assumed that type.cyclictree.ordering is given already for multiple leading eigenvectors.
% if v0 is empty, then otherwise
% if v0 is given, then v0s must be given too
% if smpflag is not given, then it is assumed all given orderings are smps
% if multiplicity is not given, and not computed, it is set to one.
%
% Written by tommsch, 2018

% XX Test ob alle orderings Spaltenvektoren sind. Testen für: orderings von restarts, orderings berechnet, orderings übergeben per parameter
% XX Teste spectralradius der Kandidaten. Dann kann ich mir smpflag sparen zu übergeben.
% XX Wenn mehrere orderingens für einen cand gegeben sind, teste ob alle diese orderings den gleichen eigenvektor haben

    type.info.infotext=vprintf('Make smp-candidates. \n','imp',[2,type.opt.verbose],'str',type.info.infotext);
    dim=size(M{1},2); %the dimension
    if(iscell(type.cyclictree.smpflag)); error('''smpflag'' must be given as a vector.'); end; %test if smpflag is a vector (and not a cell array)
    if(~isempty(type.cyclictree.ordering) && isempty(type.cyclictree.smpflag)); type.cyclictree.smpflag=zeros(1,size(type.cyclictree.ordering,2)); end; %if smpflag is not given and orderings are not empty, then all orderings are candidates
    oo_mult={}; noo_mult={}; extravertex={}; %initialize variables
    oo_single={}; noo_single={};
    
    %We first store everything in temporary variables (oo_single/_mult), noo_single/_mult, v0mult, v0smult, extravertex, ... .
    %Then we store it in the struct type.cyclictree
    if(isempty(type.cyclictree.ordering)) 
        %if no ordering is given, compute orderings (i.e. candidates and nearlycandidates)
        [oo_single, noo_single, type.info.findsmp]=findsmp(M,'maxsmpdepth',type.opt.maxsmpdepth,'verbose',type.opt.verbose-1,'N',type.opt.findsmp_N,'minJSR',type.opt.minJSR(1),'nearlycandidate',type.opt.nearlycandidate); 
        type.JSR=intersectinterval(type.info.findsmp.jsrbound,type.JSR,'failsafe','minmax'); %update bounds for JSR
        if(type.opt.nearlycandidate==0); noo_single={}; end;  %if nearlycandidates shall not be used
        if(size(oo_single,2)>type.opt.maxnumcandidate*type.info.dim); type.info.errorcode=TJSR_TOOMUCHCANDIDATE;  return; end; %if too much candidates were found
    elseif(isempty(type.cyclictree.v0)) 
        %no eigenvectors are given
        oo_single=type.cyclictree.ordering(type.cyclictree.smpflag==0); %orderings are given, but no eigenvectors. We still have to compute multiple eigenvectors v0 and v0s for each orderings
        noo_single=type.cyclictree.ordering(type.cyclictree.smpflag==1); 
        if(min(cellfun(@(x) size(x,2),oo_single))>max(cellfun(@(x) size(x,1),oo_single))^type.counter.nummatrix);
            type.info.infotext=vprintf('The array of orderings is probably transposed. Each ordering must be a column!\n','cpr','err','imp',[0,type.opt.verbose],'str',type.info.infotext);
            type.info.errortest=vprintf('The array of orderings is probably transposed. Each ordering must be a column!\n','cpr','err','imp',[0,type.opt.verbose],'str',type.info.infotext);
        end
    elseif(isempty(type.cyclictree.v0s) && ~isempty(type.cyclictree.v0)) 
        %orderings are given, v0 is given, v0s is not given. We set v0s to zero.  We do not have to compute eigenvectors any more.
        oo_mult=type.cyclictree.ordering(type.cyclictree.smpflag==0); 
        noo_mult=type.cyclictree.ordering(type.cyclictree.smpflag==1);    
        v0_mult=type.cyclictree.v0(type.cyclictree.smpflag==0); 
        nearlyv0_mult=type.cyclictree.v0(type.cyclictree.smpflag==1); 
        v0s_mult=v0_mult; [v0s_mult{:}]=deal(zeros(dim,1));
        nearlyv0s_mult=noo_mult; [nearlyv0s_mult{:}]=deal(zeros(dim,1));
        extravertex=type.cyclictree.v0(type.cyclictree.smpflag==2); 
        if(isempty(type.cyclictree.multiplicity)); 
            nearlymultiplicity=ones(1,sum(type.cyclictree.smpflag==1));
            multiplicity=ones(1,sum(type.cyclictree.smpflag==0));
        end;
        if(min(cellfun(@(x) size(x,2),oo_mult))>max(cellfun(@(x) size(x,1),oo_mult))^type.counter.nummatrix);
            type.info.infotext=vprintf('The array of orderings is probably transposed. Each ordering must be a column!\n','cpr','err','imp',[0,type.opt.verbose],'str',type.info.infotext);
            type.info.errortest=vprintf('The array of orderings is probably transposed. Each ordering must be a column!\n','cpr','err','imp',[0,type.opt.verbose],'str',type.info.infotext);
        end
    else
        %orderings are given and leading eigenvectors. We do not have to compute eigenvectors any more.
        oo_mult=type.cyclictree.ordering(type.cyclictree.smpflag==0); 
        noo_mult=type.cyclictree.ordering(type.cyclictree.smpflag==1);    
        v0_mult=type.cyclictree.v0(type.cyclictree.smpflag==0); 
        nearlyv0_mult=type.cyclictree.v0(type.cyclictree.smpflag==1); 
        extravertex=type.cyclictree.v0(type.cyclictree.smpflag==2); 
        v0s_mult=type.cyclictree.v0s(type.cyclictree.smpflag==0);     
        nearlyv0s_mult=type.cyclictree.v0s(type.cyclictree.smpflag==1);    
        if(isempty(type.cyclictree.multiplicity)); 
            nearlymultiplicity=ones(1,sum(type.cyclictree.smpflag==1));
            multiplicity=ones(1,sum(type.cyclictree.smpflag==0));
        end;
        if(min(cellfun(@(x) size(x,2),oo_mult))>max(cellfun(@(x) size(x,1),oo_mult))^type.counter.nummatrix);
            type.info.infotext=vprintf('The array of orderings is probably transposed. Each ordering must be a column!\n','cpr','err','imp',[0,type.opt.verbose],'str',type.info.infotext);
            type.info.errortest=vprintf('The array of orderings is probably transposed. Each ordering must be a column!\n','cpr','err','imp',[0,type.opt.verbose],'str',type.info.infotext);
        end        
    end
    if(~isempty(type.cyclictree.extravertex)); 
        %if extravertices are given with the option 'extravertex'
        if(~iscell(type.cyclictree.extravertex)); error('''extravertex'' must be given as a cell array of column vectors.'); end;
        extravertex=[extravertex type.cyclictree.extravertex];
    end
    %delete unnecessary fields in type.cyclictree
    type.cyclictree=rmfield(type.cyclictree,'extravertex');
    
    %compute multiple eigenvectors if needed
    if(isempty(oo_mult) && isempty(noo_mult)); %if we still need to compute multiple eigenvectors
        type.info.infotext=vprintf('Compute eigenvectors. \n','imp',[2,type.opt.verbose],'str',type.info.infotext);
        [oo_mult,       v0_mult,       v0s_mult,       multiplicity] =  leadingeigenvector(M, oo_single,      'epsequal',type.opt.epsequal, 'nomultipleeigenvector', type.opt.nomultipleeigenvector,'verbose',type.opt.verbose-1,'complexeigenvector',type.opt.complexeigenvector,'cycle',20*(~type.opt.noclassify),'repetition',50*(~type.opt.noclassify));
        if(~isequal(type.info.algorithm,TJSR_COMPLEXFUNCT)); complexeigenvector=3; else; complexeigenvector=type.opt.complexeigenvector; end;
        [noo_mult, nearlyv0_mult, nearlyv0s_mult, nearlymultiplicity] = leadingeigenvector(M, noo_single,'epsequal',type.opt.epsequal, 'nomultipleeigenvector', type.opt.nomultipleeigenvector,'verbose',type.opt.verbose-1,'complexeigenvector',complexeigenvector,'cycle',20*(~type.opt.noclassify),'repetition',50*(~type.opt.noclassify));
    end
    
    if(type.opt.nearlycandidate==0); noo_mult={}; nearlyv0_mult={}; nearlyv0s_mult={}; end;
    v0property=identifymatrix([v0_mult nearlyv0_mult extravertex]);
    if(type.info.matrixtype.nonneg && ~v0property.nonneg); %Even if the matrices are nonnegative, there could be multiple leading eigenvectors, of which one has negative entries.
        if(isequal(type.info.algorithm,0) || isempty(type.info.algorithm))
            type.info.infotext=vprintf('Warning: Nonnegative matrices with non-nonnegative leading eigenvector. Non-nonnegative eigenvectors are removed and|or rounded towards zero.\nAlgorithm (P) is used (cone-norm). \nIf Minkowski-norm (Algorithm (R)) shall be used, add <''algorithm'',''R''> as option.\n','cpr','err','imp',[1,type.opt.verbose],'str',type.info.infotext);
            if(isempty(type.info.algorithm)); type.info.errortext=vprintf('Warning: Nonnegative matrices with non-nonnegative leading eigenvector. Non-nonnegative eigenvectors are removed and|or rounded towards zero. Algorithm (P) is used (cone-norm)\n','cpr','err','imp',[1,type.opt.verbose],'str',type.info.errortext); end;
            for i=1:size(v0_mult,2); 
                idx=v0_mult{i}>-10*eps & v0_mult{i}<0; v0_mult{i}(idx)=0; 
                idx=v0s_mult{i}>-10*eps & v0s_mult{i}<0; v0s_mult{i}(idx)=0;
            end;
            idx=cellfun(@(x) any(x<0),v0_mult);       
            v0_mult(idx)=[];       v0s_mult(idx)=[];       oo_mult(idx)=[];       multiplicity(idx)=[];
            for i=1:size(nearlyv0_mult,2); 
                idx=nearlyv0_mult{i}<-10*eps & nearlyv0_mult{i}<0; nearlyv0_mult{i}(idx)=0; 
                idx=nearlyv0s_mult{i}<-10*eps & nearlyv0s_mult{i}<0; nearlyv0s_mult{i}(idx)=0;
            end;
            idx=cellfun(@(x) any(x<0),nearlyv0_mult); 
            nearlyv0_mult(idx)=[]; nearlyv0s_mult(idx)=[]; noo_mult(idx)=[]; nearlymultiplicity=[];
        elseif(isequal(type.info.algorithm,1))
            type.info.infotext=vprintf('Warning: Nonnegative matrices with non-nonnegative leading eigenvector.\nAlgorithm (R) is used (Minkowski-norm).\nIf cone-norm (Algorithm (P)) shall be used, add <''algorithm'',''P''> as option.\n','cpr','err','imp',[1,type.opt.verbose],'str',type.info.infotext);
            type.info.errortext=vprintf('Warning: Nonnegative matrices with non-nonnegative leading eigenvector. Algorithm (R) is used (Minkowski-norm)\n','cpr','err','imp',[1,type.opt.verbose],'str',type.info.errortext);
            type.info.algorithm=1;            
        end
    end
    type.info.infotext=vprintf('Set to choose from (these are not the final candidates!):\n','imp',[3,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('Maximum multiplicity of leading eigenvectors: %i\n', max(multiplicity),'imp',[3,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('Candidates %v\n', oo_mult,     'imp',[3,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('Multiplicity of candidates:        %v\n', multiplicity,     'imp',[3,type.opt.verbose],'str',type.info.infotext);
    if(nearlymultiplicity); type.info.infotext=vprintf('Multiplicity of nearly candidates: %v\n', nearlymultiplicity,'imp',[3,type.opt.verbose],'str',type.info.infotext); end;
    
    %choose best orderings
    if(~type.opt.noclassify); type.info.infotext=vprintf('If it takes too long, use option <''noclassify'',1> and mabye <''delta'',.99999>.\n','imp',[2 type.opt.verbose],'str',type.info.infotext); end;
    type.info.infotext=vprintf('Classify leading eigenvectors.\n','imp',[2,type.opt.verbose],'str',type.info.infotext);
    
    v0=[v0_mult nearlyv0_mult extravertex];
    v0s=[v0s_mult nearlyv0s_mult num2cell(zeros(type.info.dim,size(extravertex,2)),1)];
    cand=[oo_mult noo_mult num2cell(zeros(1,size(extravertex,2)),1)]; %cand must be a cell array
    idx=cellfun(@(x) size(x,2),cand)>1; cand=cellfun(@(x,y) tif(y,x',x), cand,num2cell(idx),'UniformOutput',false); %make all orderings to column vectors
    mult=[multiplicity nearlymultiplicity ones(1,length(extravertex))];
    smpflag=[0*ones(1,length(v0_mult)) 1*ones(1,length(nearlyv0_mult)) 2*ones(1,length(extravertex))];
    [v0, v0s, oo, smpflag, mult, type] = tjsr_selectordering(v0, v0s, cand, smpflag, mult, type); %select smp-candidates
    orho=cellfun(@(x) max(abs(eig(tbuildproduct(M, removezero(x(:,1),'all')))))^(1/length(removezero(x(:,1),'all'))),oo); orho=orho./max(orho); orho(smpflag==0)=1;
    
    
    type=tjsr_setproblemtype( type, v0property ); %sets the value of type.info.algorithm
    
    %compute spectral radius of candidate
    if(isempty(oo_mult));
        type.lambda=1;
    else
        type.lambda=trho(tbuildproduct(M,oo_mult{1}(:,1)))^(1/length(oo_mult{1}(:,1)));
    end
    if(type.lambda==0); return; end;
    
    
    %add extravertices in svd-directions
    if(type.opt.autoextravertex);
        autoextravertex=tjsr_autoextravertex(M,type, [oo_mult noo_mult], [v0_mult nearlyv0_mult]);
        nautoextravertex=length(autoextravertex);
        v0=[v0 autoextravertex];
        v0s=[v0s num2cell(zeros(type.info.dim, nautoextravertex),1)]; 
        oo=[oo, repcell([],1,nautoextravertex)];
        orho=[orho, NaN*ones(1,nautoextravertex)];
        smpflag=[smpflag 2*ones(1,nautoextravertex)];
        mult=[mult 1*ones(1,nautoextravertex)];
    end
    
    type.info.infotext=vprintf('Selected candidates: \n%v\n',oo(smpflag==0),'imp',[2,type.opt.verbose],'str',type.info.infotext);
    if(~isempty(noo_mult)); type.info.infotext=vprintf('Selected nearlycandidates: \n%v\n',oo(smpflag==1),'imp',[2,type.opt.verbose],'str',type.info.infotext); end;
    type.info.infotext=vprintf('Number of candidates (with multiples): %i\n',nnz(smpflag==0),'imp',[2,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('Number of nearlycandidates (with multiples): %i\n',nnz(smpflag==1),'imp',[2,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('Number of extravertices: %i\n',nnz(smpflag==2),'imp',[1,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('v0: \n%v\n',v0,'imp',[3,type.opt.verbose],'str',type.info.infotext);
    type.info.infotext=vprintf('v0s: \n%v\n',v0s,'imp',[3,type.opt.verbose],'str',type.info.infotext);
    %if(~isempty(extravertex)); type.info.infotext=vprintf('Extravertices: \n%v\n',extravertex,'imp',[1,type.opt.verbose],'str',type.info.infotext); end;
    

    %save everything in 'type'
    type.counter.numcandidate=nnz(smpflag==0);
    type.counter.numnearlycandidate=nnz(smpflag==1);
    type.counter.numextravertex=nnz(smpflag==2);
    type.counter.numordering=length(smpflag);
    
    type.cyclictree.orho=           orho;
    type.cyclictree.smpflag=        smpflag;
    type.cyclictree.ordering=       oo;
    type.cyclictree.v0=             v0;
    type.cyclictree.v0s=            v0s;
    type.cyclictree.multiplicity=   mult;
    type.cyclictree.oclass=         oo;
    type.cyclictree.maxlengthordering= cellfun(@(x) size(x,1), oo);
     
    if((any(cellfun(@(x) any(isnan(x)),type.cyclictree.v0s)) || any(type.cyclictree.multiplicity>1)) && type.opt.testeigenplane>-inf); 
        type.info.infotext=vprintf('Eigenplane-termination-criterium cannot be used.\n','imp',[1,type.opt.verbose],'str',type.info.infotext);
        type.opt.testeigenplane=-inf; 
    end;
    
end


function [v0, v0s, oo, smpflag, mult, type] = tjsr_selectordering(v0, v0s, oo, smpflag, mult, type);
    %checks if there are multiple eigenvectors, and put same eigenvectors into the same class
    %repeats orderings and cycles orderings to find more matches
    %returns everything as row vector   
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%%These are values for a non-trivial example to test the algorithm
    % Ex1:
    % % tjsr({[2 1; 0 -2],[2 0; -1 -2]},'invariantsubspace','none','maxsmpdepth',1,'verbose',2)
    % % tjsr(tgallery('ex_rand_rho',2,2,7),'invariantsubspace','none','verbose',3,'nearlycandidate',0.99,'maxsmpdepth',10,'nobalancing')
    %
    % Ex2:
%     v0_mult={}; nv0_mult={}; o_mult={}; no_mult={};  %DEBUG
%     v0_mult{1}=[1;1];v0_mult{10}=[1;1];
%     v0_mult{2}=[2;2];v0_mult{9}=[2;2];v0_mult{6}=[2;2];
%     v0_mult{13}=[3;3];v0_mult{4}=[3;3];v0_mult{7}=[3;3];
%     v0_mult{8}=[4;4];v0_mult{11}=[4;4];
%     v0_mult{12}=[5;5];
%     v0_mult{5}=[6;6];
%     v0_mult{3}=[7;7];
%     nv0_mult{1}=[-1;-1];
%      
%     o_mult{1}=[2 1]; o_mult{2}=[1 2]; o_mult{13}=[1 2 1 2];
%     o_mult{4}=[1 3 3]; o_mult{5}=[3 3 1]; o_mult{6}=[3 1 3];
%     o_mult{7}=[2]; o_mult{8}=[2 2];
%     o_mult{9}=[1 3]; o_mult{10}=[1 3 1 3]; o_mult{11}=[3 1 3 1]; o_mult{12}=[3 1];
%     o_mult{3}=[3];
%     no_mult{1}=[1 2 3];
    %
    % Ex3:
%     v0={};  oo={};   %DEBUG
%     oo{1}=[1 1 1 1 2]; oo{2}=[1 1 1 2 1]; oo{3}=[1 1 2 1 1]; oo{4}=[1 2 1 1 1]; oo{5}=[2 1 1 1 1]; 
%     oo{6}=[1 2]; oo{7}=[1 2];
%     oo{8}=[1]; oo{9}=[2]; oo{10}=[2];
%     v0{1}=[1;1]; v0{2}=[2;2];v0{3}=[3;3]; v0{4}=[4;4];v0{5}=[5;5];
%     v0{6}=[1;1]; v0{7}=[2;2];
%     v0{8}=[3;3]; v0{9}=[6;6]; v0{10}=[10;10];
%     smpflag=[0 0 0 0 0 1 1 1 1 2];
%     mult=[1 1 1 1 1 2 2 3 3 3];
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    if(any(cellfun(@(x) size(x,2),oo)>1)); return; end;
    if(size(oo,2)==1); return; end;
    o_short=reducelength(oo);
    
    type.info.infotext=vprintf('   Compute classes of eigenvectors and orderings (clusters) - ','imp',[3,type.opt.verbose],'str',type.info.infotext);
    val=[v0{:}]; val=[real(val); imag(val)]; val=val+2*abs(min(min(val)))+1; %workaround for strange behaviour of uniquetol: if one entry is zero, uniquetol behaves like unique
    [~,idx_vs_v0class,idx]=uniquetol(val',type.opt.epsequal,'ByRows',true);
    [~,idx_vs_v0class]=sort(idx_vs_v0class); [~,idx_vs_v0class]=sort(idx_vs_v0class); %remove "holes" in the numbering off class
    idx_vs_v0class=idx_vs_v0class(idx).'; %if v0class{i}==v0class{j} then v0{i}==v0{j}

    [~,idx_vs_o,idx]=uniquecell(oo);
    [~,idx_vs_o]=sort(idx_vs_o); [~,idx_vs_o]=sort(idx_vs_o); %remove "holes" in the numbering off class
    idx_vs_o=idx_vs_o(idx).'; %if oclass{i}==oclass{j} then allo(i)==allo(j)
    
    [~,idx_vs_oclass,idx]=uniquecell(o_short);
    [~,idx_vs_oclass]=sort(idx_vs_oclass); [~,idx_vs_oclass]=sort(idx_vs_oclass); %remove "holes" in the numbering off class
    idx_vs_oclass=idx_vs_oclass(idx).'; %if oclass{i}==oclass{j} then reducelength(i)==reducelength(j)
        
    type.info.infotext=vprintf('   %i eigenvector(s), %i ordering(s) found.\n',max(idx_vs_v0class), max(idx_vs_oclass),'imp',[3,type.opt.verbose],'str',type.info.infotext);
    
    %partitionate problem in subproblems
    type.info.infotext=vprintf('   Compute connectivity between clusters, partitionate problem in subproblems - ','imp',[3,type.opt.verbose],'str',type.info.infotext);
    v0class_vs_oclass=cell(1,max(idx_vs_v0class)); 
    for i=1:length(v0class_vs_oclass); 
        v0class_vs_oclass{i}=sort(idx_vs_oclass(idx_vs_v0class==i)); 
        v0class_vs_oclass{i}=unique(v0class_vs_oclass{i});
    end; 
    v0class_vs_o=cell(1,max(idx_vs_v0class)); 
    for i=1:length(v0class_vs_o); 
        v0class_vs_o{i}=sort(idx_vs_o(idx_vs_v0class==i)); 
        v0class_vs_o{i}=unique(v0class_vs_o{i});
    end; 
    
    
    %look which v0-class hits which ordering-class    
    v0class_vs_oclass_2=v0class_vs_oclass; %oclass_2 is actually the same as "problem"
    for i=1:length(v0class_vs_oclass_2); for j=i+1:length(v0class_vs_oclass_2) %#ok<ALIGN>
        if(intersect(v0class_vs_oclass_2{i},v0class_vs_oclass_2{j}));
            v0class_vs_oclass_2{i}=union(v0class_vs_oclass_2{i},v0class_vs_oclass_2{j}); v0class_vs_oclass_2{j}=v0class_vs_oclass_2{i}; %union all v0_classes
        end
    end; end;

    %each different v0_class_2 is a problem
    [~,~,v0class_vs_problem]=uniquecell(v0class_vs_oclass_2); v0class_vs_problem=v0class_vs_problem';
    type.info.infotext=vprintf('   %i subproblem(s) found.\n',max(v0class_vs_problem),'imp',[3,type.opt.verbose],'str',type.info.infotext);
    
    problem_vs_oclass=cell(1,max(v0class_vs_problem)); 
    problem_vs_v0class=cell(1,max(v0class_vs_problem));
    for i=1:max(v0class_vs_problem); 
        problem_vs_oclass{i}=unique(cell2mat(v0class_vs_oclass(v0class_vs_problem==i)));    %compute which ordering-indices belong to the subproblems
        problem_vs_v0class{i}=find(v0class_vs_problem==i);                          %compute which v0-indices belong to the subproblems
    end; 

    if(type.opt.noclassify)
        idx_all=num2cell(1:length(v0));
    else
    
        %solve problem for each sub-problem
        %XX if there are too many candidates, we cant compute all combinations and thus need to make some trivial choice
        type.info.infotext=vprintf('   Choose candidates for each subproblem.\n','imp',[3,type.opt.verbose],'str',type.info.infotext);
        idx_v0class=cell(size(problem_vs_oclass));
        for i=1:max(v0class_vs_problem);
            %make all possible choices of eigenvectors
            v0choice={}; 
            for j=1:numel(problem_vs_oclass{i});
                v0choice=[v0choice num2cell(combnk(problem_vs_v0class{i},j),2)']; %#ok<AGROW>
            end;  
            type.info.infotext=vprintf('   Size of subproblem no. %i: %i.',i,length(v0choice),'imp',[3,type.opt.verbose],'str',type.info.infotext);

            %test if choice covers whole problem
            ocovered=cell(1,length(v0choice));
            for j=1:length(v0choice); 
                for k=1:length(v0choice{j}); 
                    ocovered{j}=[ocovered{j}, idx_vs_oclass(idx_vs_v0class(:)==v0choice{j}(k))]; %compute which clusters are covered
                end; 
                ocovered{j}=unique(ocovered{j}); 
            end; 
            idx=find(cellfun(@(x) isequal(x,problem_vs_oclass{i}), ocovered)); %save which choices cover everything



            %choose the choice with minimal length  of orderings involved
            type.info.infotext=vprintf('   Compute weights.','imp',[3,type.opt.verbose],'str',type.info.infotext);        
            CUMWEIGHT=inf*ones(size(v0choice)); %initialize variable, set to infinity so that I can use min(WEIGHT) afterwards
            for j=idx %go through every possible choice                
                CUMWEIGHT(j)=0; %set to zero, since I want to add up numbers
                for k=1:length(v0choice{j});
                    CAND=idx_vs_v0class==v0choice{j}(k); %choose candidates
                    CUMWEIGHT(j)=CUMWEIGHT(j)+min(cellfun(@length, oo(CAND))); %add length of candidates to the WEIGHT
                end;
            end;
            idx=intersect(idx,find(CUMWEIGHT==min(CUMWEIGHT)));

            %choose the idx with minimal ordering-length of v0choice(idx)
            LENGTH=(cellfun(@length, v0choice(idx)));
            idx=idx(LENGTH==min(LENGTH));

            %choose the idx with least ordering-weight of v0choice(idx) %XX Test what happens with multiple leading ev
            WEIGHT=cellfun(@numel ,v0choice(idx));
            %
            %WEIGHT=cellfun(@(x) ordering2num({x,[]},max([v0choice{idx}])),v0choice(idx));
            idx=idx(WEIGHT==min(WEIGHT));


            allv0_idx=[v0choice{idx(1)}]; %make idx point to (original) allv0

            idx_v0class{i}=allv0_idx(:).'; %choose all minimal lengths
            type.info.infotext=vprintf('   Subproblem solved.\n','imp',[3,type.opt.verbose],'str',type.info.infotext);
        end;
        idx_v0class=[idx_v0class{:}];
        idx_all=arrayfun(@(x) find(idx_vs_v0class==x),idx_v0class,'UniformOutput',0);
    end
    
    
    v0=cellfun(@(x) v0(x(1)),idx_all);
    v0s=cellfun(@(x) v0s(x(1)),idx_all);
    
    val=oo;
    %put all orderings together
    for i=1:length(idx_all)
        val2=uniquecell(reducelength(val(idx_all{i}),1));
        val2=removecombination(val2);
        maxSize = max(cellfun(@numel, val2));               % Get the maximum vector size
        padd = @(x) [x; zeros(maxSize-numel(x),1)];             % Create an anonymous function
        oo{i} = cellfun(padd, val2, 'UniformOutput', false);  % Pad each cell with 0
        oo{i} = cell2mat(oo{i});                             % Vertically concatenate cells
        
    end
    oo(length(idx_all)+1:end)=[];
    
    mult=cellfun(@(x) max(mult(x)),idx_all);
    smpflag=cellfun(@(x) min(smpflag(x)),idx_all);

    type.info.infotext=vprintf('   Everything done.\n','imp',[3,type.opt.verbose],'str',type.info.infotext);
end

function [Vextra,type] = tjsr_autoextravertex(M, type, cand, v0);

    %compute whole cycle (very ugly to do it here) but I don't want to change the whole program.
    for i=1:length(M)
        M{i}=M{i}./type.lambda;
    end
    VV=cell(1,length(cand));

    for i=1:length(cand)
        oo=arrayfun(@(x) cand{i}(1:x),  1:length(cand{i}),'UniformOutput',0);
        val=cellfun(@(x) tbuildproduct(M, x)*v0{i}, oo,'UniformOutput',0);
        VV{i}=[val{:}];
    end
    VV=[VV{:}];
    
    if(type.info.algorithm==TJSR_CONEFUNCT)
        idx=max(VV,[],2)<type.opt.autoextravertex;
        Vextra=eye(size(VV,1));
        Vextra=Vextra(:,idx);
        
    elseif(type.info.algorithm==TJSR_MINKFUNCT);
        [U,SVD,~]=svd(VV);
        if(~isvector(SVD)); SVD=diag(SVD); end; %make singular values to a vector
        if(length(SVD)<type.info.dim); SVD(type.info.dim)=0; end; %fill up with zeros
        rat=SVD/max(SVD); 
        idx=rat<type.opt.autoextravertex;
        Vextra=normalizematrix(U(:,idx),'positive',1);
        
    elseif(type.info.algorithm==TJSR_COMPLEXFUNCT);
        type.info.infotext=vprintf('''autoextravertex'' for complex case not yet implemented.\n','cpr','err','imp',[3,type.opt.verbose],'str',type.info.infotext);
        dim=size(v0{1},1);
        Vextra=zeros(dim,0);
    else
        error('Unkown alorithm given. This should not happen.');
    end;
    Vextra=num2cell(Vextra,1);
end

function val = TJSR_TOOMUCHCANDIDATE;               val=130; end %findsmp found too much candidates %this function is also defined in tjsr_makecandidate!!!

function dummy; end %#ok<DEFNU> %Generates an error, if the 'end' of a function is missing. 