Tentukan Node di Jaringan dengan PostgreSQL

Question

Saya memiliki tabel di mana setiap entri adalah node dan tabel berisi koneksi langsung dari setiap node ke node lain. Saya ingin membuat tampilan dengan kolom untuk setiap node yang berisi semua node dalam rantai, bukan hanya node yang terhubung ke node itu sendiri.

Contoh akan menghasilkan kolom Nodes in Chain dari dua kolom pertama dari tabel berikut:

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

Itu adalah versi kecil yang disederhanakan dari masalah sebenarnya. Jika saya bisa menyelesaikan contoh, tabel penuh seharusnya tidak ada masalah.

Data tabel ini dapat divisualisasikan sebagai berikut:

Saya telah melihat beberapa metode berbeda untuk menyelesaikan masalah ini. Saya telah memeriksa CTE rekursif tetapi saya belum berhasil membuatnya berfungsi.

Setiap node terhubung ke dirinya sendiri saat ini di database. Tidak masalah untuk menghapus koneksi ke dirinya sendiri dalam database jika itu diperlukan.

Mungkin latar belakang masalah yang tidak perlu :

Asal mula masalah ini berasal dari upaya untuk mengidentifikasi kendaraan di lalu lintas. Database asli berisi lokasi dan kecepatan kendaraan pada setiap langkah waktu t di area tertentu. Tujuannya adalah untuk menentukan waktu yang dihabiskan di lampu lalu lintas. Untuk mengatasi masalah ini, area berhenti untuk lampu lalu lintas diidentifikasi. Setiap kendaraan di kawasan ini dengan kecepatan di bawah ambang tertentu dianggap menunggu lampu lalu lintas. Karena antrian panjang, kendaraan mungkin mengantri di luar area ini. Oleh karena itu, dibuat garis lalu lintas ("Rantai Node") dengan semua kendaraan yang berada dalam jarak tertentu satu sama lain dan memiliki kecepatan rendah di bawahnya. Mulai dari kendaraan dalam area antrian yang teridentifikasi. Masalahnya adalah bagian dari penelitian ilmiah tentang waktu taksi pesawat. Karenanya, kendaraan tersebut adalah pesawat terbang dan lampu merah adalah ambang landasan pacu.

Saya pertama kali melakukan perhitungan untuk mengidentifikasi kendaraan di suatu daerah dengan Python dan panda. Namun kode tersebut membutuhkan waktu 10x lebih lama untuk dijalankan yang membuatnya menjadi penghalang bagi proyek. Kode ini sangat sederhana tanpa loop yang diperkenalkan secara manual dan oleh karena itu tidak dapat dipercepat (saya yakin). Saya juga akan membandingkan kecepatan melakukan algoritma antrian dengan Python versus PostgreSQL.

Answer 1

Pendekatan 1:

Pada pandangan pertama, tampaknya saya dapat menerapkan solusi dasar karena, menurut data sampel Anda, setiap koneksi disertakan dalam koneksi lain.

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;

simpul | koneksi | node_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}         

Pendekatan 2:

Namun, seperti yang ditunjukkan @ypercube , solusi ini tidak berfungsi jika ada 3 atau lebih titik linier dalam satu baris.

Contoh: e -> f -> g -> h

Sebagai referensi untuk menjawab pertanyaan ini, saya menggunakan jawaban dalam pertanyaan terkait lainnya:

• Mengelompokkan salah satu dari beberapa kolom di Postgres

Ini menggunakan metode yang disebut penutupan transitif untuk menyelesaikan masalah.

Penutupan transitif

Dalam matematika, penutupan transitif dari relasi biner R pada himpunan X adalah relasi terkecil pada X yang mengandung R dan bersifat transitif.

Misalnya, jika X adalah himpunan bandara dan xRy berarti "ada penerbangan langsung dari bandara x ke bandara y" (untuk x dan y di X), maka penutupan transitif dari R di X adalah relasi R + sehingga x R + y berarti "memungkinkan untuk terbang dari x ke y dalam satu penerbangan atau lebih". Secara informal, penutupan transitif memberi Anda kumpulan semua tempat yang bisa Anda datangi dari tempat awal mana pun.

Pertama izinkan saya mengubah data sampel Anda dengan menambahkan koneksi linier dari 4 node.

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

Sekarang menerapkan matematika:

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;

Beri kami hasil ini:

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 <> biola di sini

CATATAN : Relasi asli hanya memiliki koneksi langsung, yang dapat dilihat sebagai jalur dengan panjang 1 (masing-masing 2 node). Pendekatan 1 menemukan semua jalur dengan panjang 2 (3 node) karena menerapkan metode menghubungkan sekali. Untuk menemukan jalur dengan panjang N, Anda harus menerapkan metode N-1 kali. Untuk menemukan semua jalur dengan panjang sembarang (sayangnya penutupan transitif), Anda memerlukan solusi rekursif, atau loop sementara. Ini tidak dapat dilakukan dengan SQL sederhana. (yaitu: satu kueri tanpa CTE.)

_@detikcom