在PostgreSQL中查找给定的集群节点 [英] Find cluster given node in PostgreSQL

问题描述

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

I am representing a graph in Postgres 9.1 (happens to be bidirectional and cyclic):

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，想要检索该群集中的所有其他节点。我从单个节点的路径示例开始此处，这就是我得到的地方：

Given a particular node ID, want to retrieve all other nodes in that cluster. I started with the "Paths from a single node" example here, and this is where I got:

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）如果有更简单的方法可以写这个，因为我不不必担心收集完整的路径，并且b）如何使其在两个方向上都遍历（ node1 -> node2 和 node2 -> node1 ）。尽量避免使用任何好的方法。谢谢！

I can't figure out a) if there is a simpler way to write this since I don't care about collecting the full path, and b) how to make it traverse in both directions (node1->node2 and node2->node1 for each edge). Shedding any light on a good approach would be appreciated. Thanks!

推荐答案

几点。

首先，你真的想要确保您的路径遍历不会陷入循环。其次，处理双方都还不错。最后，根据您要执行的操作，您可能希望以某种方式将where子句推入CTE，以减少生成每个可能的图形网络，然后选择所需的图形网络。

First, you really want to make sure your path traversal is not going to go into a loop. Secondly handling both sides is not too bad. Finally depending on what you are doing, you may want to push the where clause into the CTE somehow to reduce generating every possible graph network and then picking the one you want.

遍历两个方向本身并不难。我还没有测试过，但是应该可以通过以下方式实现：

Traversing itself both directions is not too hard. I haven't tested this but it should be possible with something like:

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

希望这会有所帮助。

这篇关于在PostgreSQL中查找给定的集群节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！