루프에 대한 재귀 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