detect cycles in a graph in SQL using recursive common table expression

Given a directed graph having a cycle, how do you detect and list the cycle using only standard SQL ? input = graph edges and a root node from which we compute the transitive closure. Output = listing of nodes in the cycle.

Answer

CREATE TABLE #myEdge ( ID INT IDENTITY(1,1) PRIMARY KEY, NodeIDFrom INT, NodeIDTo INT )

INSERT INTO #myEdge(NodeIDFrom, NodeIDTo) VALUES (4, 5),(5, 6),(6, 4);

DECLARE @rootNode AS integer = 4;

–compute the transitive closure from this root. column Niveau holds the recursion nesting level.

WITH cte_transitive_closure(rootNode, NodeFrom, NodeTo, Niveau) AS ( SELECT @rootNode, NULL, @rootNode, 0

UNION ALL

SELECT rootNode, e.NodeIDFrom, e.NodeIDTo, Niveau+1
FROM cte_transitive_closure AS cte
JOIN #myEdge AS e ON cte.NodeTo=e.NodeIdFrom
WHERE Niveau < 99

) SELECT * INTO #transitive_closure FROM cte_transitive_closure;

SELECT * FROM #transitive_closure;

–starting from root as a reached target, move back in the trace until the root is hit again.

WITH cte_cycle(NodeFrom, NodeTo, Cycle) AS ( SELECT @rootNode,NULL,0

UNION ALL

SELECT t.NodeFrom, t.NodeTo, 0
FROM cte_cycle AS cte
JOIN #transitive_closure AS t ON cte.NodeFrom = t.NodeTo
WHERE t.NodeFrom != @rootNode AND Cycle=0

UNION ALL

SELECT t.NodeFrom, t.NodeTo, 1
FROM cte_cycle AS cte
JOIN #transitive_closure AS t ON cte.NodeFrom = t.NodeTo
WHERE t.NodeFrom = @rootNode AND Cycle=0

) SELECT DISTINCT * FROM cte_cycle;

result set:

NodeFrom -> NodeTo (Cycle)

4 -> NULL (0)

4 -> 5 (1)

5 -> 6 (0)

6 -> 4 (0)