Explodir pesquisa de profundidade no UNIX

Question

Tenho os seguintes dados no arquivo que têm relação de usuário e supervisor.

user |supervisor |id
-----|-----------|----
a    |   b       | 1
b    |   c       | 2
c    |   d       | 3
e    |   b       | 4

Eu quero explodir a hierarquia de relacionamento entre o usuário e o supervisor, conforme abaixo.

user |supervisor |id
-----|-----------|----
a    |   b       | 1
a    |   c       | 1
a    |   d       | 1
b    |   c       | 2
b    |   d       | 2  
c    |   d       | 3
e    |   b       | 4
e    |   c       | 4
e    |   d       | 4 

Como você vê, para o usuário 'a', o supervisor imediato é 'b', mas novamente 'b' tem 'c' como seu supervisor. Então, indiretamente, 'c' é supervisor de 'a' e assim por diante. Tal como, meu objetivo é explodir a hierarquia em qualquer nível para um determinado usuário. Qual é a melhor maneira de implementar isso no Unix?

    

Answer 1

Estou assumindo que cada usuário aparece no arquivo de entrada (na coluna "Usuário") apenas uma vez. Além disso, suponho que os separadores da barra vertical ( | ) estão realmente no arquivo, e que eles são sempre separados dos dados por espaço em branco, e que a linha de cabeçalho não está presente .

Veja uma solução de duas etapas usando awk . O primeiro passo cria um array contendo o supervisor de todos; o segundo passo constrói a saída:

awk 'pass==1 { super[$1] = $3; }
     pass==2 {
                print
                user=$3
                while (super[user] != "") {
                        print $1, "|", super[user], "|", $5
                        user=super[user]
                }
             }
    ' pass=1 data pass=2 data

Isso produzirá resultados que não estão alinhados corretamente. Para corrigir isso, canalize-o em column -t . Ou podemos formatar a saída de dentro do script awk ; se você quiser, especifique as regras de formatação desejadas.

A propósito, esta operação é geralmente conhecida como encerramento transitivo .

    

Answer 2

Solução awk complexa:

awk 'NR<3{ h=(h=="")? $0 : h ORS $0 }NR>2{ uid[$1]=$5; us[$1]=$3 }
     END{ 
         print h; 
         for (u in uid) { 
             id=uid[u]; spvr=us[u]; printf("%-5s|%-11s|%-4s\n",u,spvr,id); 
             while (spvr in uid) { 
                 spvr=us[spvr]; printf("%-5s|%-11s|%-4s\n",u,spvr,id) 
             } 
         }
     }' yourfile

A saída:

user |supervisor |id
-----|-----------|----
a    |b          |1   
a    |c          |1   
a    |d          |1   
b    |c          |2   
b    |d          |2   
c    |d          |3   
e    |b          |4   
e    |c          |4   
e    |d          |4 

Detalhes:

• NR<3{ h=(h=="")? $0 : h ORS $0 } - capturando cabeçalho linhas

• uid[$1]=$5 - user-id matriz de relações

• us[$1]=$3 - user-supervisor relação matriz

• spvr=us[u] - o primeiro supervisor para o atual usuário

• while (spvr in uid) { ... } - enquanto o supervisor está na lista usuário , obtém supervisor pai p>

Answer 3

Minha solução awk (usando formatos de saída de RomanPerekhrest). Basicamente, existem dois loops relevantes. Primeiro, se um novo supervisor for processado para um usuário, todas as dependências desse supervisor (ou seja, cadeias de supervisor) devem ser adicionadas ao usuário. Depois disso, um segundo loop procura todos os outros usuários, que têm o usuário atualmente processado como uma dependência e todas as dependências do usuário atual são adicionadas a eles.

#!/usr/bin/awk
# file process_it.awk
BEGIN {

    FS="|";
}

NR<3 {

    h=(h==""? $0 : h ORS $0)
}

NR>2 {

   gsub(/ /, "", $0)
   curr_user=$1;
   curr_supervisor=$2;
   curr_id=$3;
   print curr_user, curr_supervisor;
   arr[curr_user][curr_supervisor]++;
   id[curr_user]=curr_id;

   if(isarray(arr[curr_supervisor])) {
       for(sub_indx in arr[curr_supervisor])
           arr[curr_user][sub_indx]++;
    }
    else
        delete arr[curr_supervisor];

    for(indx in arr) {

        if(isarray(arr[indx])) {

            for(sub_indx in arr[indx]) {

                if(sub_indx==curr_user) {

                    for(sub_indx2 in arr[curr_user])
                    arr[indx][sub_indx2]++;
                }
            }    
        }
    }
}

END {
    print h;

    for(i in arr) {

        if(isarray(arr[i])) {

            for(j in arr[i])
                printf "%-5s|%-11s|%-3s\n", i, j, id[i];
        }
    }
}

Uso:

awk -f process_it.awk your_file.txt