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 に答える