查找集群节点给出PostgreSQL中

我代表了在Postgres 9.1的图形（恰好是双向和循环）：查找集群节点给出PostgreSQL中

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，要检索该群中的其他节点。我开始与例如here的“从单个节点路径”，而这正是我：

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

我想不出一个），如果有，因为我不写这个简单的方法关心收集完整的path，以及b）如何使它在两个方向上移动（node1 - >node2和node2 - >node1）。谢谢你的一个好方法，任何灯光将不胜感激。谢谢！

来源

2012-09-03 Aidan Feldman

一般来说，我会省略'edges.id'列，并使用两个对'nodes'的引用作为复合主键，可能也会以相反顺序引用它们作为唯一索引。除非需要有多个相同的链接，否则'edges.id'列只是自重。 – kgrittn

当然 - 这是一个简单化。还会有其他属性绑定到边缘，零边或更多边连接任何两个节点，因此复合主键不会是唯一的。 –

有几点。

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

虽然第三行的WHERE条件不适用于每个递归吗？我只得到那个节点。 –

它不应该。我们一直使用它进行树递归。 –

这是我的测试：http://sqlfiddle.com/#!1/1dc18/2（p.s.我刚刚搜索了“sql小提琴”和......谁知道！？） –

查找集群节点给出PostgreSQL中

回答

相关问题