在递归查询中检测周期

Question

我的PostgreSQL数据库中有一个有向图，节点和循环之间可以有多个路径：

create table "edges" ("from" int, "to" int);
insert into "edges" values (0, 1), (1, 2), (2, 3), (3, 4), (1, 3);
insert into "edges" values (10, 11), (11, 12), (12, 11);

我想找到一个节点和与其连接的每个节点之间的最小边数：

with recursive "nodes" ("node", "depth") as (
  select 0, 0
union
  select "to", "depth" + 1
  from "edges", "nodes"
  where "from" = "node"
) select * from "nodes";

返回所有路径的深度：

 node  0 1 2 3 3 4 4 
 depth 0 1 2 2 3 3 4

 0 -> 1 -> 2 -> 3 -> 4
 0 -> 1 ------> 3 -> 4

我需要最低限度，但 递归查询的递归项中不允许使用聚合函数

with recursive "nodes" ("node", "depth") as (
  select 0, 0
union
  select "to", min("depth") + 1
  from "edges", "nodes"
  where "from" = "node"
  group by "to"
) select * from "nodes";

但是，对结果使用聚合函数可以：

with recursive "nodes" ("node", "depth") as (
  select 0, 0
union all
  select "to", "depth" + 1
  from "edges", "nodes"
  where "from" = "node"
) select * from (select "node", min("depth")
                 from "nodes" group by "node") as n;

预期回报

node  0 1 2 3 4
depth 0 1 2 2 3

但是，进入循环会导致无限循环，并且 对查询“节点”的递归引用一定不能出现在子查询中 ，因此我无法检查是否已访问节点：

with recursive "nodes" ("node", "depth") as (
  select 10, 0
union
  select "to", "depth" + 1
  from "edges", "nodes"
  where "from" = "node"
  and "to" not in (select "node" from "nodes")
) select * from "nodes";

我在这里寻找的结果是

node  10 11 12
depth  0  1  2

有没有办法用递归查询/通用表表达式来做到这一点？

另一种方法是创建一个临时表，迭代添加行，直到用完为止。即呼吸优先搜索。

Answer 1

您可以根据文档在查询中添加周期检测

with recursive "nodes" ("node", "depth", "path", "cycle") as (
  select 10, 0, ARRAY[10], false
union all
  select "to", "depth" + 1, path || "to", "to" = ANY(path)
  from "edges", "nodes"
  where "from" = "node" and not "cycle"
) select * from (select "node", min("depth"), "path", "cycle"
                from "nodes" group by "node", "path", "cycle") as n 
                where not "cycle";

该查询将返回您期望的数据