有向无环图：找到特定节点的所有路径 [英] Directed acyclic graph: find all paths from a specific node

问题描述

如何找到特定节点（示例中为节点36）的所有路径？

How do I find all the paths from a specific node (node 36 in the example)?

假设我们有两个表：

CATEGORIES      CATEG_PARENTS
id              idc  | idparent
--              ----------------
1               2      1
2               2      20
5               5      2
8               8      5
20              20     1
22              22     8
30              22     20
31              30     20
36              31     22
                31     30
                36     31

这是两种可能的表示形式：

These are two possible representations:

）

_{（来源：位于nebm.ist.utl.pt的问题）}

这是我想要的输出：

ids
-------------------
"{1,20,22,31}"
"{1,20,2,5,8,22,31}"
"{1,20,30,31}"
"{1,2,5,8,22,31}"

每行一条路径，写为整数数组。

One path per line, written as an integer array.

（我要写出我想出的答案，但我会接受任何更简单的答案，如果有的话）

(I'm going to write the answer I came up with, but I'll accept any that's simpler, if any)

推荐答案

WITH RECURSIVE parent_line(path, id) AS (
    SELECT ARRAY[(row_number() OVER (PARTITION BY CP.idc))::integer], C.id
    FROM categorias C JOIN categ_parents CP ON C.id = CP.idparent
    WHERE CP.idc = 36
    UNION ALL
    SELECT PL.path || (row_number() OVER (PARTITION BY PL.id))::integer,
        C.id
    FROM categorias C
    JOIN categ_parents CP ON C.id = CP.idparent
    JOIN parent_line PL on CP.idc = PL.id
),
real_parent_line(path, chainid, id) AS (
    SELECT PL.path, (row_number() OVER (PARTITION BY PL.id)),
        PL.id
    FROM parent_line PL
    WHERE PL.id IN (
        SELECT id
        FROM categorias C LEFT JOIN categ_parents CP
            ON (C.id = CP.idc)
        WHERE CP.idc IS NULL
    )
    UNION ALL
    SELECT PL.path, chainid, PL.id
    FROM parent_line PL, real_parent_line RPL
    WHERE array_upper(PL.path,1) + 1 = array_upper(RPL.path,1)
        AND PL.path = RPL.path[1:(array_upper(RPL.path,1)-1)]
)
SELECT array_accum(id) AS ids
FROM real_parent_line RPL
GROUP BY chainid;

第一个 WITH 子句给出以下内容：

The first WITH clause gives this:

path             | id
------------------------
"{1}"              31
"{1,1}"            22
"{1,2}"            30
"{1,1,1}"          20
"{1,1,2}"          8
"{1,2,1}"          20
"{1,1,2,1}"        5
"{1,1,1,1}"        1
"{1,2,1,2}"        1
"{1,1,2,1,1}"      2
"{1,1,2,1,1,1}"    1
"{1,1,2,1,1,2}"    20
"{1,1,2,1,1,2,1}"  1

感谢＃postgresql @ freenode寻求帮助。

Thanks to #postgresql@freenode for some help.

这篇关于有向无环图：找到特定节点的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！