循環的遞歸CTE停止條件

Question

我需要使用遞歸CTE迭代帶有循環的圖。

問題是迴路部分。

我想要如果有循環，然後選擇最短的路徑。 這基本上意味着忽略循環，因爲遞歸是「寬度優先」。

下面的示例顯示了返回的數據：

的問題是註釋掉INSERT語句創建了一個循環。 顯然，它沒有註釋，查詢將永遠不會結束。

我需要的是返回與沒有循環相同的數據。

DROP TABLE IF EXISTS edges; 

CREATE TABLE edges(
    src integer, 
    dst integer, 
    data integer 
); 

INSERT INTO edges VALUES (1, 2, 1); 
INSERT INTO edges VALUES (2, 3, 1); 
--INSERT INTO edges VALUES (3, 2, 1); -- This entry creates a loop 
INSERT INTO edges VALUES (1, 4, 1); 
INSERT INTO edges VALUES (4, 5, 1); 
INSERT INTO edges VALUES (5, 2, 1); 

INSERT INTO edges VALUES (1, 4, 2); 
INSERT INTO edges VALUES (4, 5, 2); 
INSERT INTO edges VALUES (4, 6, 2); 


WITH RECURSIVE paths AS (
    -- For simplicity assume node 1 is the start 
    -- we'll have two starting nodes for data = 1 and 2 
    SELECT DISTINCT 
    src   as node 
    , data  as data 
    , 0   as depth 
    , src::text as path 
    FROM edges 
    WHERE 
    src = 1 

    UNION ALL 

    SELECT DISTINCT 
    edges.dst 
    , edges.data 
    , depth + 1 
    , paths.path || '->' || edges.dst::text 
    FROM paths 
    JOIN edges ON edges.src = paths.node AND edges.data = paths.data 
    -- AND eliminate loops? 
) 

SELECT * FROM paths; 

返回：

node | data | depth |  path  
------+------+-------+--------------- 
    1 | 1 |  0 | 1 
    1 | 2 |  0 | 1 
    2 | 1 |  1 | 1->2 
    4 | 1 |  1 | 1->4 
    4 | 2 |  1 | 1->4 
    3 | 1 |  2 | 1->2->3 
    5 | 2 |  2 | 1->4->5 
    6 | 2 |  2 | 1->4->6 
    5 | 1 |  2 | 1->4->5 
    2 | 1 |  3 | 1->4->5->2 
    3 | 1 |  4 | 1->4->5->2->3 
(11 rows) 

Answer 1

WITH RECURSIVE paths AS (
    -- For simplicity assume node 1 is the start 
    -- we'll have two starting nodes for data = 1 and 2 
    SELECT DISTINCT 
     src   as node 
     , data  as data 
     , 0   as depth 
     , src::text as path 
     , ''   as edgeAdded 
    FROM edges 
    WHERE 
     src = 1 

    UNION ALL 

    SELECT DISTINCT 
     edges.dst 
     , edges.data 
     , depth + 1 
     , paths.path || '->' || edges.dst::text 
     , edges.src::text || '->' || edges.dst::text 
    FROM paths 
    JOIN edges ON edges.src = paths.node AND edges.data = paths.data 
    AND NOT paths.path LIKE '%' || edges.dst::text || '%' 
     -- AND eliminate loops? 
) 
SELECT * FROM paths; 

這裏與條件AND NOT paths.path LIKE '%' || edges.dst::text || '%'我們避免背部邊緣，這將導致一個循環。
http://www.sqlfiddle.com/#!12/086ee/1