Trouver un cluster avec un nœud donné dans PostgreSQL

Question

Je représente un graphe dans Postgres 9.1 (qui se trouve être bidirectionnel et cyclique) :

CREATE TABLE nodes (
  id          SERIAL PRIMARY KEY,
  name        text
);

CREATE TABLE edges (
  id          SERIAL PRIMARY KEY,
  node1_id    int REFERENCES nodes(id),
  node2_id    int REFERENCES nodes(id)
);

Étant donné un ID de nœud particulier, je veux récupérer tous les autres nœuds dans ce cluster. J'ai commencé par l'exemple "Chemins à partir d'un seul noeud". aquí et c'est là que je suis arrivé :

WITH RECURSIVE search_graph(id, path) AS (
    SELECT id, ARRAY[id]
    FROM nodes
  UNION
    SELECT e.node2_id, sg.path || e.node2_id
    FROM search_graph sg
    JOIN edges e
    ON e.node1_id = sg.id
)
-- find all nodes connected to node 3
SELECT DISTINCT id FROM search_graph WHERE path @> ARRAY[3];

Je n'arrive pas à savoir a) s'il y a une manière plus simple d'écrire ceci puisque je ne me soucie pas de collecter l'intégralité de l'information. path et b) comment le faire traverser dans les deux sens ( node1 -> node2 y node2 -> node1 pour chaque bord). Je vous serais reconnaissant de m'éclairer sur une bonne approche. Merci.

Answer 1

Quelques points.

Tout d'abord, vous devez vraiment vous assurer que votre parcours ne va pas tourner en boucle. Ensuite, le traitement des deux côtés n'est pas trop difficile. Enfin, en fonction de ce que vous faites, vous pouvez pousser la clause where dans le CTE d'une manière ou d'une autre pour réduire la génération de tous les réseaux de graphes possibles et ensuite choisir celui que vous voulez.

Se déplacer dans les deux sens n'est pas trop difficile. Je ne l'ai pas testé mais cela devrait être possible avec quelque chose comme :

WITH RECURSIVE search_graph(path, last_node1, last_node2) AS (
     SELECT ARRAY[id], id, id
     FROM nodes WHERE id = 3 -- start where we want to start!
     UNION ALL
     SELECT sg.path || e.node2_id || e.node1_id, e.node1_id, e.node2_id
     FROM search_graph sg
     JOIN edges e
     ON (e.node1_id = sg.last_node2 AND NOT path @> array[e.node2_id]) 
        OR (e.node2_id = sg.last_node1 AND NOT path @> array[e.node1_id])
 )
-- Moved where clause to start of graph search
SELECT distinct unnest(path) FROM search_graph;  -- duplicates possible

J'espère que cela vous aidera.