3

我在 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每个边缘）。对一个好的方法有任何启发将不胜感激。谢谢！

4

1 回答 1

2

几点。

首先，你真的想确保你的路径遍历不会进入循环。其次处理双方也不错。最后，根据您在做什么，您可能希望以某种方式将 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

希望这可以帮助。

于 2012-09-03T06:46:48.797 回答