PostgreSQL SQL 查询遍历整个无向图并返回找到的所有边

Question

我的 PostgreSQL 数据库中有一个 edges table 代表 directed 的边图，有两列：node_from 和 node_to（值是节点的 ID）。

给定一个节点（initial_node）我希望能够遍历整个图，但是在无向方式。

我的意思是，例如下图：

(a->b)
(c->b)
(c->d)

如果initial_node是a,b,c，或d，无论如何，我会得到[a，b, c, d].

我使用了以下 SQL 查询（基于 http://www.postgresql.org/docs/8.4/static/queries-with.html ）：

WITH RECURSIVE search_graph(uniq, depth, path, cycle) AS (
        SELECT
          CASE WHEN g.node_from = 'initial_node' THEN g.node_to ELSE g.node_from END,
          1,
          CASE WHEN g.node_from = 'initial_node' THEN ARRAY[g.node_from] ELSE ARRAY[g.node_to] END,
          false
        FROM edges g
        WHERE 'initial_node' in (node_from, node_to)
      UNION ALL
        SELECT
          CASE WHEN g.node_from = sg.uniq THEN g.node_to ELSE g.node_from END,
          sg.depth + 1,
          CASE WHEN g.node_from = sg.uniq THEN path || g.node_from ELSE path || g.node_to END,
          g.node_to = ANY(path) OR g.node_from = ANY(path)
        FROM edges g, search_graph sg
        WHERE sg.uniq IN (g.node_from, g.node_to) AND NOT cycle
)
SELECT * FROM search_graph

它工作得很好......直到我有一个案例有 12 个节点，它们在各个方向都连接在一起（对于每一对，我都有 (a->b) 和 (b->a)），这使得查询无限循环。（将 UNION ALL 更改为 UNION 不会消除循环。）

有人对处理这个问题有什么建议吗？

干杯，

安托万。

Answer 1

我明白了，它不应该与任何类型的数据陷入无限循环：

--create temp table edges ("from" text, "to" text);
--insert into edges values ('initial_node', 'a'), ('a', 'b'), ('a', 'c'), ('c', 'd');

with recursive graph(points) as (
  select array(select distinct "to" from edges where "from" = 'initial_node')
  union all
  select g.points || e1.p || e2.p
  from graph g
  left join lateral (
    select array(
      select distinct "to"
      from edges 
      where "from" =any(g.points) and "to" <>all(g.points) and "to" <> 'initial_node') AS p) e1 on (true)
  left join lateral (
    select array(
      select distinct "from"
      from edges 
      where "to" =any(g.points) and "from" <>all(g.points) and "from" <> 'initial_node') AS p) e2 on (true)
  where e1.p <> '{}' OR e2.p <> '{}'
  )
select distinct unnest(points)
from graph
order by 1

递归查询在可以 selected 方面非常有限，并且由于它们不允许在子 select 中使用递归结果，所以不能使用 NOT IN （select * 来自递归 where...）。将结果存储在数组中，使用 LEFT JOIN LATERAL 并使用 =ANY() 和 <>ALL() 解决了这个难题。

PostgreSQL SQL 查询遍历整个无向图并返回找到的所有边

PostgreSQL SQL query for traversing an entire undirected graph and returning all edges found

postgresql

recursion

traversal

graph