在递归查询中检测周期 [英] Detecting cycles in a recursive query

问题描述

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

I have a directed graph in my PostgreSQL database, there can be multiple paths between nodes and cycles:

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);

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

I'd like to find the minimum number of edges between a node and every node connected to it:

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";

在结果上使用聚合函数虽然可行：

Using an aggregate function on the result works though:

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

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

However, running into the cycle causes an infinite loop, and recursive reference to query "nodes" must not appear within a subquery, so I can't check if a node has already been visited:

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

是否可以通过递归查询/通用表表达式来做到这一点？

Is there a way to do this with recursive queries / common table expressions?

另一种方法是创建一个临时表，迭代添加行直到耗尽为止；即第一次呼吸。

The alternative would be to create a temporary table, iteratively adding rows until exhausted; i.e. a breath first search.

相关：此答案检查如果该节点已经包含在路径中并避免了循环，但仍无法避免进行不必要的工作，即检查出比已知的最短路径更长的路径，因为它的行为仍像深度优先搜索

related: this answer checks if the node is contained in the path already and avoids loops, but still can't avoid doing the unnecessary work of checking out paths that are longer than the shortest known one because it's still behaving like a depth first search

推荐答案

您可以基于文档

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";

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

This query will return data you expected

这篇关于在递归查询中检测周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！