Eu tenho uma tabela onde cada entrada é um nó e a tabela contém as conexões diretas de cada nó com outros nós. Estou procurando criar uma exibiçã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 tabela a seguir:
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 puder resolver o exemplo, a tabela completa não deve ser problema.
Os dados desta tabela podem ser visualizados da seguinte forma:
Eu olhei em vários métodos diferentes para resolver este problema. Eu olhei para 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 para si mesmo no banco de dados, se necessário.
Provavelmente antecedentes desnecessários 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 a cada passo de tempo t em uma determinada área. O objetivo é determinar o tempo gasto em um semáforo. Para solucionar 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 fila, os veículos podem, no entanto, fazer fila fora desta área. Portanto, é feita uma linha de tráfego ("Cadeia de Nós") com todos os veículos que estão a uma certa distância uns dos outros e possuem uma velocidade baixa abaixo. Partida de um veículo dentro da área de fila identificada. O problema faz parte da pesquisa científica sobre os tempos de táxi das aeronaves.
Primeiro realizei o cálculo para identificar veículos em uma área com Python e pandas. No entanto, o código demorou 10x 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 poderia ser acelerado (acredito). Também vou comparar a velocidade de execução do algoritmo de enfileiramento em Python versus PostgreSQL.