Рекурсивное условие остановки 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