Determinar nós na rede com PostgreSQL

Question

Eu tenho uma tabela onde cada entrada é um nó e a tabela contém as conexões diretas de cada nó para outros nós. Estou procurando criar uma visualização com uma coluna para cada nó contendo todos os nós da cadeia, não apenas os nós aos quais o próprio nó está conectado.

Um exemplo seria gerar a coluna Nodes in Chain a partir das duas primeiras colunas da seguinte tabela:

CREATE TABLE example
(
    node text,
    connections text[],
    nodes_in_chain text[]
)

INSERT INTO example VALUES
('a', ARRAY['a','b'],         null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'],         null),
('d', ARRAY['b','d'],         null),
('e', ARRAY['e','f'],         null),
('f', ARRAY['e','f'],         null);

Node   Connections    Nodes in Chain
"a"    "{a,b}"        "{a,b,c,d}"
"b"    "{a,b,c,d}"    "{a,b,c,d}"
"c"    "{b,c}"        "{a,b,c,d}"
"d"    "{b,d}"        "{a,b,c,d}"
"e"    "{e,f}"        "{e,f}"
"f"    "{e,f}"        "{e,f}"

Essa é uma pequena versão simplificada do problema real. Se eu conseguir resolver o exemplo, a tabela completa não deve ser problema.

Os dados desta tabela podem ser visualizados da seguinte forma:

Eu pesquisei vários métodos diferentes para resolver esse problema. Eu pesquisei CTEs recursivos, mas não consegui fazê-los funcionar.

Cada nó está conectado a si mesmo atualmente no banco de dados. Não é um problema remover a conexão com ele mesmo no banco de dados, se isso for necessário.

Histórico provavelmente desnecessário para o problema :

A origem desse problema vem da tentativa de identificar veículos no trânsito. O banco de dados original contém a localização e a velocidade dos veículos em cada etapa t em uma determinada área. O objetivo é determinar o tempo gasto em um semáforo. Para resolver este problema, foi identificada uma área de parada para o semáforo. Cada veículo nesta área com uma velocidade abaixo de um determinado limite é considerado como aguardando o semáforo. Devido a uma longa fila de espera, os veículos podem, no entanto, estar na fila fora desta área. Portanto, uma linha de tráfego ("Cadeia de Nós") é feita com todos os veículos que estão a uma certa distância uns dos outros e têm uma baixa velocidade abaixo. Partindo de um veículo dentro da área de fila identificada. O problema faz parte da pesquisa científica sobre os tempos de taxiamento de aeronaves. Os veículos são, portanto, aeronaves e os semáforos são os limites da pista.

Primeiro executei o cálculo para identificar veículos em uma área com Python e pandas. No entanto, o código demorou 10 vezes mais para ser executado, o que o tornou proibitivo para o projeto. O código era muito simples, sem loops introduzidos manualmente e, portanto, não podia ser acelerado (acredito). Também estarei comparando a velocidade de execução do algoritmo de enfileiramento em Python versus PostgreSQL.

Answer 1

Abordagem 1:

À primeira vista, parece que eu poderia aplicar uma solução básica porque, de acordo com seus dados de amostra, cada conexão individual está incluída em outra conexão.

SELECT 
    e1.node, 
    e1.connections, 
    COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
    example e1
LEFT JOIN 
    example e2
    ON e2.node <> e1.node
    AND e1.connections <@ e2.connections;

nó | conexões | nodes_in_chain
: --- | : ---------- | : -------------
a | {a, b} | {a, b, c, d}     
b | {a, b, c, d} | {a, b, c, d}     
c | {b, c} | {a, b, c, d}     
d | {b, d} | {a, b, c, d}     
e | {e, f} | {e, f}         
f | {e, f} | {e, f}         

Abordagem 2:

Mas, como @ypercube apontou, essa solução não funciona se houver 3 ou mais pontos lineares em uma linha.

Ex: e -> f -> g -> h

Como referência para resolver esta questão, usei as respostas de outra questão relacionada:

• Agrupamento em qualquer uma das várias colunas do Postgres

Ele usa um método chamado fechamento transitivo para resolver o problema.

Fechamento transitivo

Em matemática, o fechamento transitivo de uma relação binária R em um conjunto X é a menor relação em X que contém R e é transitiva.

Por exemplo, se X é um conjunto de aeroportos e xRy significa "há um vôo direto do aeroporto x para o aeroporto y" (para xey em X), então o fechamento transitivo de R em X é a relação R + tal que x R + y significa "é possível voar de x para y em um ou mais voos". Informalmente, o fechamento transitivo fornece o conjunto de todos os lugares aos quais você pode chegar a partir de qualquer ponto de partida.

Primeiro, deixe-me alterar seus dados de amostra adicionando uma conexão linear de 4 nós.

DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'],     null),
('g', ARRAY['f','g','h'],     null),
('h', ARRAY['g','h'],         null);

Agora aplicando a matemática:

WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
  SELECT e1.node, e2.node
  FROM   example e1
  JOIN   example e2
         ON e1.node = any(e2.connections)   
), tc (dst, src) AS
   (
     SELECT dst, src FROM al -- transitive closure
     UNION
     SELECT a1.dst, a2.src
     FROM   al as a1 
     JOIN   tc as a2 
            ON a1.src = a2.dst
   )
   SELECT   src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
   FROM     tc
   GROUP BY src;

Dê-nos este resultado:

src | nodes_in_chain
:-- | :-------------
a   | {a,b,c,d}     
b   | {a,b,c,d}     
c   | {a,b,c,d}     
d   | {a,b,c,d}     
e   | {e,f,g,h}     
f   | {e,f,g,h}     
g   | {e,f,g,h}     
h   | {e,f,g,h}     

db <> fiddle aqui

NOTA : A relação original possui apenas as conexões imediatas, que podem ser vistas como caminhos de comprimento 1 (2 nós cada). A abordagem 1 encontra todos os caminhos de comprimento 2 (3 nós), pois aplica um método de conexão única. Para encontrar caminhos de comprimento N, você deve aplicar os métodos N-1 vezes. Para encontrar todos os caminhos de comprimentos arbitrários (infelizmente, o fechamento transitivo), você precisa de uma solução recursiva ou um loop while. Isso não pode ser feito com SQL simples. (ou seja: uma consulta sem CTEs.)

_@ypercube