Determina i nodi in rete con PostgreSQL

Question

Ho una tabella in cui ogni voce è un nodo e la tabella contiene le connessioni dirette di ogni nodo ad altri nodi. Sto cercando di creare una vista con una colonna per ogni nodo contenente tutti i nodi della catena, non solo i nodi a cui è connesso il nodo stesso.

Un esempio potrebbe essere la generazione della colonna Nodi in catena dalle prime due colonne della seguente tabella:

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}"

Questa è una piccola versione semplificata del vero problema. Se riesco a risolvere l'esempio, la tabella completa non dovrebbe essere un problema.

I dati di questa tabella possono essere visualizzati nel modo seguente:

Ho esaminato diversi metodi per risolvere questo problema. Ho esaminato i CTE ricorsivi ma non sono riuscito a farli funzionare.

Ogni nodo è connesso a se stesso attualmente nel database. Non è un problema rimuovere la connessione a se stesso nel database, se necessario.

Probabilmente sfondo non necessario per il problema :

L'origine di questo problema deriva dal tentativo di identificare i veicoli nel traffico. Il database originale contiene la posizione e la velocità dei veicoli in ogni fase t in una determinata area. L'obiettivo è determinare il tempo trascorso a un semaforo. Per risolvere questo problema è stata individuata un'area di sosta per il semaforo. Ogni veicolo in quest'area con una velocità inferiore a una certa soglia è considerato in attesa del semaforo. A causa di una lunga coda, i veicoli potrebbero comunque essere in coda fuori da quest'area. Pertanto una linea di traffico ("Catena di nodi") viene realizzata con tutti i veicoli che si trovano entro una certa distanza l'uno dall'altro e hanno una bassa velocità al di sotto. Partendo da un veicolo all'interno dell'area di coda identificata. Il problema fa parte della ricerca scientifica sui tempi di taxi degli aerei. I veicoli sono quindi aerei e i semafori sono soglie di pista.

Per prima cosa ho eseguito il calcolo per identificare i veicoli in un'area con Python e panda. Tuttavia, l'esecuzione del codice ha richiesto 10 volte più tempo, il che lo ha reso proibitivo per il progetto. Il codice era molto semplice senza loop introdotti manualmente e quindi non poteva essere accelerato (credo). Confronterò anche la velocità di esecuzione dell'algoritmo di accodamento in Python rispetto a PostgreSQL.

Answer 1

Approccio 1:

A prima vista, sembra che potrei applicare una soluzione di base perché, secondo i tuoi dati di esempio, ogni singola connessione è inclusa in un'altra connessione.

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;

nodo | connessioni | 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}         

Approccio 2:

Ma, come ha sottolineato @ypercube , questa soluzione non funziona se ci sono 3 o più punti lineari di seguito.

Es: e -> f -> g -> h

Come riferimento per risolvere questa domanda ho usato le risposte in un'altra domanda correlata:

• Raggruppamento su una qualsiasi delle più colonne in Postgres

Utilizza un metodo chiamato chiusura transitiva per risolvere il problema.

Chiusura transitiva

In matematica, la chiusura transitiva di una relazione binaria R su un insieme X è la più piccola relazione su X che contiene R ed è transitiva.

Ad esempio, se X è un insieme di aeroporti e xRy significa "c'è un volo diretto dall'aeroporto x all'aeroporto y" (per xey in X), allora la chiusura transitiva di R su X è la relazione R + tale che x R + y significa "è possibile volare da x a y in uno o più voli". Informalmente, la chiusura transitiva ti dà l'insieme di tutti i luoghi a cui puoi arrivare da qualsiasi punto di partenza.

Per prima cosa lasciami modificare i tuoi dati di esempio aggiungendo una connessione lineare di 4 nodi.

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);

Ora applicando la matematica:

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;

Dacci questo risultato:

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 qui

NOTA : la relazione originale ha solo le connessioni immediate, che possono essere viste come percorsi di lunghezza 1 (2 nodi ciascuno). L'approccio 1 trova tutti i percorsi di lunghezza 2 (3 nodi) poiché applica un metodo di connessione una volta. Per trovare percorsi di lunghezza N, devi applicare i metodi N-1 volte. Per trovare tutti i percorsi di lunghezza arbitraria (ahimè la chiusura transitiva), è necessaria una soluzione ricorsiva, o un ciclo while. Non può essere fatto con un semplice SQL. (ad esempio: una query senza CTE.)

_@ypercube