查找集羣節點給出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中

回答

相關問題