Como agrupar valores com base em uma métrica de "conectividade"?

Question

Existe um arquivo com três colunas. As colunas 1 e 2 contêm números do mesmo conjunto. O arquivo normalmente terá uma linha para cada par de membros do conjunto; então, se houver membros n , deve haver n × ( n −1) / 2 linhas.

A coluna 3 mostra a quantidade de conexões entre os números nas colunas 1 e 2.

Eu quero particionar meu conjunto de fontes em grupos de valores consecutivos (isto é, intervalos) para os quais a ligação é maior ou igual a 0,2. Por exemplo, neste pequeno conjunto de dados:

entrada:

1   2       0.222
1   3       0.213
1   4       0.014
1   5       0.001
1   6       0.555
1   7       0.509
2   3       0.213
2   4       0.014
2   5       0.001
2   6       0.555
2   7       0.709
2   8       0.509
3   4       0.995
3   5       0.323
3   6       0.555
3   7       0.225
3   8       0.001
4   5       0.095
4   6       0.058
4   7       0.335
4   8       0.005
5   6       0.995
5   7       0.658
5   8       0.650
6   7       0.431
6   8       0.333
7   8       0.754

a saída deve ser como:

saída:

   G1: 1 2 3    G2: 4   G3 :5 6 7 8

A conexão entre 1 com 2 e 3 é maior que 0,2, então 1, 2 e 3 devem ser colocados no primeiro grupo. De fato, qualquer par de números dentro de um grupo deve ter conexão suficiente. Apesar da alta relação entre 1/2/3 e 6 (0,555 > 0,2), 6 não deve ser colocado no primeiro grupo, já que os números anteriores (4 e 5) tinham baixa conectividade com 1. Portanto, não devemos saltar mais de 4 e 5 e conecte os números no primeiro grupo com 6.

O número 4 não possui a alta conectividade com 5, então o número 4 deve estar no segundo grupo individualmente. Não importa que 4 tenha alta conectividade com 7, já que os números anteriores (5 e 6) estavam em baixa conectividade com 4 e não devemos pular números entre e conectar 4 com 7.

5 tem uma alta conectividade com 6, 7 e 8. Além disso, qualquer par de números (como 6/7, 6/8, 7/8) tem alta conectividade juntos. Portanto, eles devem ser colocados juntos no terceiro grupo. É por isso que todos esses números podem ser colocados em um grupo.

Observe que os dados reais não começam no número 1 e existem mais de 100.000 linhas. então é enorme.

aqui é uma parte dos meus dados reais:
entrada:

    49997 49998 0.082
    49997 49999 0.953
    49997 50000 0.060
    49998 49999 0.288
    49998 50000 0.288
    49999 50000 0.265

a saída deve ser:

  G1:49997   G3: 49998 49999 50000

    

Answer 1

Faça um loop sobre a entrada. Enquanto o primeiro número é o mesmo e a conectividade está acima do limite, adicione números ao mesmo grupo. Quando a conexão estiver muito baixa, não faça nada até encontrar o segundo número na primeira coluna.

#!/usr/bin/perl
use warnings;
use strict;

my $THRESHOLD = 0.2;

my $next;
my @groups;
while (<>) {
    my ($n1, $n2, $connectedness) = split;
    @groups = ([ $next = $n1 ]) unless defined $next;
    if ($next == $n1) {
        if ($connectedness > $THRESHOLD) {
            push @{ $groups[-1] }, $n1 unless @{ $groups[-1] };
            push @{ $groups[-1] }, $n2;

        } else {
            $next = $n2;
            push @groups, [$n2];
        }
    }
}

for my $i (1 .. @groups) {
    print "Group $i: @{ $groups[ $i - 1 ] }\n";
}