обнаружение цикла в ориентированном графе

Question

У нас есть ориентированный граф, представленный таблицей ребер.Как мы можем обнаружить цикл в чистом SQL?

CREATE TABLE edges(id integer primary key identity, from_node int, to_node int);
CREATE NONCLUSTERED INDEX index_edges_of2 ON edges(from_node);

INSERT INTO edges(from_node,to_node) VALUES(1,2),(2,3),(3,1);

Answer 1

Решением этой проблемы является рекурсивный CTE. Однако, чтобы это работало, вам нужно сохранить список посещенных узлов. SQL Server не имеет элегантного решения для этого (например, массивов), поэтому вам нужно использовать строковые манипуляции.

Ниже перечислены циклы на графике:

with cte as (
      select from_node, to_node, 
             convert(varchar(max), concat(',', from_node, ',', to_node, ',')) as nodes, 1 as lev, 
             (case when from_node = to_node then 1 else 0 end) as has_cycle
      from edges e
      union all
      select cte.from_node, e.to_node,
             convert(varchar(max), concat(cte.nodes, e.to_node, ',')), lev + 1,
             (case when cte.nodes like concat('%,', e.to_node, ',%') then 1 else 0 end) as has_cycle
      from cte join
           edges e
           on e.from_node = cte.to_node
      where cte.has_cycle = 0 
     )
select *
from cte
where has_cycle = 1;

Здесь - это скрипка db <>.

Answer 2

WITH cte AS (
    SELECT CAST('.1.' AS varchar(1000)) AS gpath, 1 AS current_node, 0 AS Cycle

    UNION ALL

    SELECT CAST(CONCAT(gpath, '.', e.to_node, '.') AS varchar(1000)) AS gpath, e.to_node AS current_node, 0 AS cycle
    FROM cte
    JOIN edges AS e ON e.from_node = cte.current_node
    WHERE CHARINDEX(CONCAT('.',e.to_node,'.'),cte.gpath)=0 AND cte.Cycle=0

    UNION ALL

    SELECT CAST(CONCAT(gpath, '.', e.to_node, '.') AS varchar(1000)) AS gpath, e.to_node AS current_node, 1 AS cycle
    FROM cte
    JOIN edges AS e ON e.from_node = cte.current_node
    WHERE CHARINDEX(CONCAT('.',e.to_node,'.'),cte.gpath)>0 AND cte.Cycle=0
)
SELECT * FROM cte;

gpath current_node Цикл

.1.1 0

.1..2.2 0

.1..2..3.3 0

.1..2..3..1.1 1