function [p, flag, C] = ordenar(D, K)
%
% determina se uma ordem de (K+1)-lateracao existe
% para uma dada matriz de distancias D
%
% INPUT:
% D: matriz de distancias
% K: dimensao de interesse
% C: (K+1)-clique inicial
%
% OUTPUT:
% p: vetor de permutacao definindo a ordem
% flag: 0 nao existe, 1 existe
%
    n = length(D);
    p = 1:n;
    C = ones(1,K+1);
    flag=0;

    % para cada clique em K+1 vertices
    % tente encontrar uma ordem de (K+1)-lateracao
    [C,p,flag] = comb(0, K, n, C, p, D, flag);

end


function [C,p,flag] = comb(idx, K, n, C, p, D, flag)

    % ordem encontrada
    if (flag) 
        return;
    end
    
    % combinacao encontrada
    if (idx == (K+1))
    
        % verificando se e' um clique
        for i=1:(K+1)
            for j=(i+1):(K+1)
                if (D(C(i),C(j))==0)
                    % nao e' um clique 
                    return;
                end     
            end
        end
        
        % tentando encontrar ordem a partir deste (K+1)-clique
        [p, flag] = trilat(D, C);
        return;
        
    end

    if (idx>=1)
        aux = C(idx);
        if ( C(idx) > (n - K + idx - 1) ) 
            return;
        end
    else
        aux = 0;
    end

    idx = idx + 1;
    i=aux;
    while  ( (i < n) && (~flag) ) 
        i=i+1;
        C(idx) = i;
        [C,p,flag] = comb(idx, K, n, C, p, D, flag);
    end
     
end

function [p, ok] = trilat(D, C)

    ok = 1;

    n = length(D);
    K = length(C) - 1;

    p = zeros(1,n);
    p(1:(K+1)) = C;
    NR = 1:n;
    NR(C) = 0;
    
    % inicializar contadores
    a = sum(D(p(1:(K+1)),:)>0,1);
    a(C) = 0;

    % atribuindo posicoes (na ordem) a vertices
    for i=(K+2):n 

        % selecione o vertice nao posicionado com maior numero de
        % adjacentes ja' posicionados
        [alpha, idx] = max(a);
        idx = idx(1);

        if (alpha<K+1)
           ok = 0;
           return
        end
        
        % incluir NR(idx) na ordem 
        p(i) = NR(idx);

        % atualizar contadores
        U = (D(:,p(i))>0); U(p(p>0))=0;
        a(U) = a(U) + 1;
        
        % remova NR(idx) de NR
        NR(idx) = 0;
        a(idx) = 0;
        
    end

end


