Find the cluster specified by node in PostgreSQL

Question

I present a graph in Postgres 9.1 (sometimes bi-directional and cyclic):

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

Given a specific node identifier, you want to get all the other nodes in this cluster. I started with the "Path from a single node" example here , and it was there that I got:

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

I cannot understand, a) if there is an easier way to write this, since I do not care about collecting the full path and b) how to make it go in both directions ( node1 → node2 and node2 → node1 for each edge). It would be helpful to evaluate any light on a good approach. Thanks!

Answer 1

A few points.

First, you really want to make sure that your path does not go in a loop. Secondly, handling both sides is not so bad. Finally, depending on what you are doing, you can somehow click the where clause in the CTE to decrease the generation of each possible network of graphs and then select the one you want.

Passing both directions is not too difficult. I have not tested this, but it should be possible with something like:

 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 

Hope this helps.