时间戳

首页 > 解决方案 > 使用 SQL 最小化图形

sql - 使用 SQL 最小化图形

问题描述

假设我们有一个定义如下的有向图：

 node | neighbor
 -----------------
   1  | 2
   1  | 3
   2  | 4
   2  | 3
   3  | 4

上表定义了两个节点之间的唯一边，(1,2)例如一对表示该节点1和2通过边连接，这是图表的图。

我还有一个图的传递闭包表，该表包含图的所有可能路径（例如：(1,3)存在两次，因为它可以直接或通过路径到达1=>2=>3），这里是表：

 node | neighbor
 -----------------
   1  | 2
   1  | 3
   2  | 4
   2  | 3
   3  | 4
   1  | 3
   1  | 4
   1  | 4
   2  | 4

从这两个表中，我想返回一个最小化的图而不失去任何可达性，一个想法是只返回不依赖于两个表的边，这是一个例子：
(1,2)在第一个表(2,3)中，在第二个表中，并且因此(1,3)可以从第一个表中删除，因为您可以通过节点到达节点3， 输出表应如下所示：12 

 node | neighbor
 -----------------
   1  | 2
   2  | 3
   3  | 4

我怎样才能编写一个 SQL 查询来做到这一点？

标签： sqlpostgresqlgraph

解决方案

这是一种方法：

with recursive cte as (
    select node, neighbor, 1 is_initial from graph
    union all 
    select c.node, g.neighbor, 0
    from cte c
    inner join graph g on g.node = c.neighbor
)
select node, neighbor
from graph g
where not exists (
        select 1 
        from cte c
        where c.node = g.node and c.neighbor = g.neighbor and c.is_initial = 0
    )
order by node, neighbor

这仅使用第一个表（我称之为graph）。我们首先使用递归查询生成所有可能的路径。这与您的闭包表非常相似，但有一个额外的列 ，is_initial表示路径是来自原始表，还是在进一步迭代期间生成。

然后，剩下要做的就是过滤图形以删除匹配“非初始”路径的元组。

DB Fiddle 上的演示：

节点 | 邻居
---: | --------:
   1 | 2
   2 | 3
   3 | 4

推荐阅读