用sql最小化图

kd3sttzy 于 2021-07-26 发布在 Java

关注(0)|答案(1)|浏览(281)

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

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) 在第一张table上 (2,3) 是在第二个，因此 (1,3) 可以从第一个表中删除，因为可以访问节点 3 从 1 通过节点 2 outuput表应该如下所示：

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

如何编写执行此操作的sql查询？

sql postgresql Graph

来源：https://stackoverflow.com/questions/62945228/minimizing-a-graph-with-sql

1条答案

按热度按时间

kmynzznz1#

这里有一种方法：

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小提琴演示：

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

赞(0）回复(0）举报 2021-07-26

我来回答

用sql最小化图

1条答案

相关问题

热门标签

最新问答