在PostgreSQL中查找集群给定节点

Question

我在Postgres 9.1中表示一个图（恰好是双向和循环的）：

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

给定一个特定的节点ID，希望检索该集群中的所有其他节点。我从这里的"单个节点的路径"示例开始，这就是我得到的：

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

我不知道a）是否有更简单的方法来写这篇文章，因为我不在乎收集完整的path，以及b）如何使它在两个方向上遍历（每个边的node1->node2和node2->node1）。如果能提供一个好的方法，我们将不胜感激。谢谢

Answer 1

几个点。

首先，您确实希望确保您的路径遍历不会进入循环。其次，处理好双方都还不错。最后，根据您正在做的事情，您可能希望以某种方式将where子句推入CTE，以减少生成每个可能的图网络，然后选择您想要的图网络。

从两个方向遍历本身并不太难。我还没有测试过这个，但它应该可以用类似的东西：

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

希望这能有所帮助。