обнаружение циклов в графе в SQL с использованием рекурсивного общего табличного выражения

Question

Для ориентированного графа, имеющего цикл, как вы можете определить и перечислить цикл, используя только стандартный SQL? input = ребра графа и корневой узел, из которого мы вычисляем транзитивное замыкание. Выходные данные = список узлов в цикле.

Answer 1

CREATE TABLE #myEdge (ID INT IDENTITY (1,1) ПЕРВИЧНЫЙ КЛЮЧ, NodeIDFrom INT, NodeIDTo INT)

INSERT INTO #myEdge (NodeIDFrom, NodeIDTo) ЗНАЧЕНИЯ (4, 5), (5,6), (6, 4);

DECLARE @rootNode AS integer = 4;

- вычислить транзитивное замыкание из этого корня.столбец Niveau содержит уровень вложенности рекурсии.

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

- начиная с корня в качестве достигнутой цели, двигаться назад по трассе до тех пор, пока корень не будет достигнут снова.

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;

набор результатов:

NodeFrom -> NodeTo (цикл)

4 -> NULL (0)

4 -> 5 (1)

5 -> 6 (0)

6 -> 4 (0)