sql detect cycle in directed graph

user_3046585 0
Viewed 710

We have a directed graph represented by an edge table. How can we detect the cycle in pure 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);
sql-server sql
2 Answers

The solution to this is a recursive CTE. However, for this to work, you need to keep a list of visited nodes. SQL Server doesn't have an elegant solution for this (such as arrays), so you need to use string manipulations.

The following will list the cycles in the graph:

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;

Here is the db<>fiddle.

user_11440350 
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 Cycle

.1. 1 0

.1..2. 2 0

.1..2..3. 3 0

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

user_30465850
Related