CODEWITHSUNDEEP
sqlsql-server
Ludovic Aubert
Ludovic Aubert

Reputation: 10526

sql detect cycle in directed graph

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);

Upvotes: 3

Views: 1386

Answers (2)

Gordon Linoff
Gordon Linoff

Reputation: 1269763

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.

Upvotes: 3

Ludovic Aubert
Ludovic Aubert

Reputation: 10526

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

Upvotes: 1

Related Questions