Postgres 递归函数唯一值

Question

我有一个图形结构

Node(pid integer)
Neighbor(pid integer, pidn integer)

Node是微不足道的，我应该说Neighbor为每个节点存储其邻居列表。这是我正在测试的图表（Neighbor关系的内容）：

PID | PIDN
==========
1   | 2
1   | 3
2   | 1
2   | 3
2   | 4
2   | 5
3   | 1
3   | 2
4   | 2
4   | 6
5   | 2
6   | 4

我想得到一个节点的所有邻居的集合，度数小于一个固定数，所以我执行以下查询：

WITH RECURSIVE search_graph(root, depth) AS (
        SELECT n.pidn, 1
        FROM node p, neighbor n
        WHERE p.pid = n.pid
        AND p.pid = 1
      UNION
        SELECT nxt.pidn, sg.depth + 1
        FROM neighbor nxt, search_graph sg
        WHERE sg.root = nxt.PID
        AND sg.depth < 3
)
SELECT * FROM search_graph s;

起始节点为 1，最大深度为 3（以防您错过它们）。我得到以下结果：

Node | Depth
============
2    | 1
3    | 1
1    | 2
3    | 2
4    | 2
5    | 2
2    | 2
2    | 3
3    | 3
1    | 3
4    | 3
5    | 3
6    | 3

因为它扩展了每个节点的所有子节点，包括访问过的子节点：

0                               1
1               2                               3
2       1    3    4    5                    1       2
3      2 3  1 2  2 6   2                   2 3   1 3 4 5

虽然我想排除访问过的孩子，但产生：

Node | Depth
============
2    | 1
3    | 1
4    | 2
5    | 2
6    | 3

我需要一种方法来将结果添加到 search_graph 仅当节点未被访问时。

Answer 1

您是否阅读过有关WITH RECURISVE的 Postgresql 文档？

有一些图表示例，其中一个看起来像是您问题的解决方案：

如果链接关系包含循环，则此查询将循环。因为我们需要一个“深度”输出，只是将 UNION ALL 更改为 UNION 不会消除循环。相反，我们需要在遵循特定的 >links 路径时识别是否再次到达同一行。我们将两列 path 和 cycle 添加到容易循环的查询中：

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
    SELECT g.id, g.link, g.data, 1,
      ARRAY[g.id],
      false
    FROM graph g
  UNION ALL
    SELECT g.id, g.link, g.data, sg.depth + 1,
      path || g.id,
      g.id = ANY(path)
    FROM graph g, search_graph sg
    WHERE g.id = sg.link AND NOT cycle
)
SELECT * FROM search_graph;