Устранить похожие циклы в ориентированном графе

Question

У меня есть следующие данные:

Таблица:

CREATE TABLE tblLoop
(
    person1 varchar(20),
    person2 varchar(20),
    ColDate date,
);

INSERT INTO tblLoop VALUES('A','B','2020-01-01'),('A','C','2020-01-01'),('A','D','2020-01-01'),
                          ('B','E','2020-01-02'),('B','F','2020-01-02'),
                          ('D','G','2020-01-03'),('D','H','2020-01-03'),
                          ('F','i','2020-01-04'),
                          ('G','J','2020-01-05'),
                          ('i','A','2020-01-06'),
                          ('J','D','2020-01-07'),
                          ('X','Y','2020-01-08'),('X','Z','2020-01-08'),
                          ('Z','X','2020-01-09'),
                          ('Y','W','2020-01-09');   

Записи выглядят так:

Требование: мне нужно найти людей, которые образуют цикл. Для примера в приведенных данных мы нашли 3 цикла:

цикл 1: A, связанный с B, связанный с F, связанный с i, связанный с A.

Цикл 2: A, связанный с D, связанный с G, связанный с J, связанный с D.

Цикл 3: X, связанный с Z, связанный с X .

Ожидаемый результат:

LoopFound
--------------------
A->B->F->i->A
A->D->G->J->D
X->Z->X

Моя попытка:

;WITH CTE AS 
(
      SELECT Person1, Person2, 
             CONVERT(VARCHAR(MAX), (','+ Person1+ ','+ Person2+ ',')) AS nodes, 1 AS lev, 
             (CASE WHEN Person1 = Person2 THEN 1 ELSE 0 END) AS has_cycle
      FROM tblLoop e
      UNION ALL
      SELECT cte.Person1, e.Person2,
             CONVERT(VARCHAR(MAX), (cte.nodes+ e.Person2+ ',')), lev + 1,
             (CASE WHEN cte.nodes LIKE ('%,'+ e.Person2+ ',%') THEN 1 ELSE 0 END) AS has_cycle
      FROM CTE 
      JOIN tblLoop e ON e.Person1 = cte.Person2
      WHERE cte.has_cycle = 0 
     )
SELECT *
FROM CTE
WHERE has_cycle = 1;

ПРИМЕЧАНИЕ : получение нескольких комбинаций циклов из запроса выше.

Answer 1

Согласно комментарию Кевина, ответ заключается в том, чтобы включить флаг, указывающий, что данный узел является допустимой начальной точкой, и может быть включен в запрос:

В этом случае 'A' и «X» задаются в качестве начальных точек, поэтому мы будем отмечать все записи, в которых инициатором является «A» или «X»:

CREATE TABLE #tblLoop
(
    person1 varchar(20),
    person2 varchar(20),
    ColDate date,
isRoot INT
);
INSERT INTO #tblLoop VALUES('A','B','2020-01-01',1),
                          ('A','C','2020-01-01',1),
                          ('A','D','2020-01-01',1),
                          ('B','E','2020-01-02',0),
                          ('B','F','2020-01-02',0),
                          ('D','G','2020-01-03',0),
                          ('D','H','2020-01-03',0),
                          ('F','i','2020-01-04',0),
                          ('G','J','2020-01-05',0),
                          ('i','A','2020-01-06',0),
                          ('J','D','2020-01-07',0),
                          ('X','Y','2020-01-08',1),
                          ('X','Z','2020-01-08',1),
                          ('Z','X','2020-01-09',0),
                          ('Y','W','2020-01-09',0);   

. Затем следующий запрос может быть изменен следующим образом:

;WITH CTE AS 
(
      SELECT Person1, Person2, isRoot,
             CONVERT(VARCHAR(MAX), (','+ Person1+ ','+ Person2+ ',')) AS nodes, 1 AS lev, 
             (CASE WHEN Person1 = Person2 THEN 1 ELSE 0 END) AS has_cycle
      FROM #tblLoop e
      UNION ALL
      SELECT cte.Person1, e.Person2, cte.isRoot,
             CONVERT(VARCHAR(MAX), (cte.nodes+ e.Person2+ ',')), lev + 1,
             (CASE WHEN cte.nodes LIKE ('%,'+ e.Person2+ ',%') THEN 1 ELSE 0 END) AS has_cycle
      FROM CTE 
      JOIN #tblLoop e ON e.Person1 = cte.Person2
      WHERE cte.has_cycle = 0 
     )
SELECT *
FROM CTE
WHERE has_cycle = 1
AND isRoot = 1

Благодарим Кевина за идею, это всего лишь рабочая реализация.

Answer 2

Я пробовал следующие два шага:

Шаг 1 : На этом шаге найдите начальные узлы графика.

--Create table to store start nodes
IF OBJECT_ID('dbo.Temp_tblLoop', 'U') IS NOT NULL 
BEGIN
  DROP TABLE dbo.Temp_tblLoop; 
END

--Query to find start nodes.
;WITH CTE AS
(
    SELECT t.* 
    FROM tblLoop t
    WHERE person1 IN (SELECT person2 FROM tblLoop t2 WHERE t.ColDate<= t2.ColDate) OR
          person2 IN (SELECT person1 FROM tblLoop t3 WHERE t.ColDate<= t3.ColDate)
)
SELECT DISTINCT person1 INTO Temp_tblLoop
FROM CTE 
WHERE person1 NOT IN (SELECT person2 FROM CTE);

Шаг 2 : Узнайте циклы на графике (исключая похожие циклы)

;WITH CTE AS 
(
      SELECT Person1, Person2, 
             CONVERT(VARCHAR(MAX), (Person1+ '->'+ Person2)) AS nodes, 1 AS lev, 
             (CASE WHEN Person1 = Person2 THEN 1 ELSE 0 END) AS has_cycle
      FROM tblLoop e WHERE person1 IN (SELECT person1 FROM Temp_tblLoop)
      UNION ALL
      SELECT cte.Person1, e.Person2,
             CONVERT(VARCHAR(MAX), (cte.nodes+'->'+ e.Person2)), lev + 1,
             (CASE WHEN CHARINDEX(e.Person2, cte.nodes) != 0 THEN 1 ELSE 0 END) AS has_cycle
      FROM CTE 
      JOIN tblLoop e ON e.Person1 = cte.Person2
      WHERE cte.has_cycle = 0 
     )
SELECT Person1 AS Start, Person2 AS [End],
       nodes AS Links,
       lev AS Levels     
FROM CTE
WHERE has_cycle = 1;    

Позвольте мне ваши отзывы, если что-то нужно сделать для улучшения.