Общие табличные выражения, как избежать бесконечного отторжения при обходе графа? - PullRequest
Новая
       15

Общие табличные выражения, как избежать бесконечного отторжения при обходе графа?

3 голосов
/ 05 марта 2010

У меня есть простой взвешенный график 

    A
 1 / \\ 0.5
  /   \\0.5
 B     C

Предположим, это описывает семью, а A - отец, B - сын, а C - мать. Допустим, Б учится в университете, а А купил для него квартиру. А живет с С в доме, который обычно принадлежит, 50-50.

Я хочу преобразовать граф в дерево, начиная с A: т.е.

  • А владеет 50% места, в котором проживает С *
  • А владеет 100% места, в котором проживает Б
  • C владеет 50% места, где проживает A

График и сгенерированное дерево могут быть более сложными, но я надеюсь, что вы получите более общую картину.

В SQL Server 2005 у меня есть 

Drop Table #graph;
Create Table #graph
    (FirstVertex VarChar(1) Not Null, 
     SecondVertex VarChar(1) Not Null, 
     Weight float);

Insert #graph Values('A','B',1);
Insert #graph Values('A','C',0.5);
Insert #graph Values('C','A',0.5);

и я использую следующее общее табличное выражение для обхода графика, начиная с 'A': 

With GraphRecursion (FirstVertex, SecondVertex, Weight, Level)
As
(
    Select FirstVertex, SecondVertex, Weight, 0 As Level
    From #graph
    Where FirstVertex='A'

    Union all

    Select a.FirstVertex, a.SecondVertex, a.Weight, b.Level+1
    From #graph a 
    Inner Join GraphRecursion b
    On a.FirstVertex=b.SecondVertex --And b.Level<=1
)
Select * From GraphRecursion;

Это вызывает 

Msg 530, Level 16, State 1, Line 11
The statement terminated. The maximum recursion 100 has 
been exhausted before statement completion.

Ограничение уровня рекурсии путем раскомментирования And b.Level<=1 дает ожидаемые результаты, но это, очевидно, не очень полезно для любого практического использования.

Есть ли способ ссылаться на предыдущие итерации, чтобы в приведенном выше примере ребра (т. Е. Пары FirstVertex, SecondVertex) не повторялись?

1 Ответ

3 голосов
/ 05 марта 2010

Вы можете создать список посещенных узлов в другом столбце, а затем запретить повторное посещение их в своей рекурсии. Примерно так (не уверен, что я выбрал правильные столбцы): 

With GraphRecursion (FirstVertex, SecondVertex, Weight, Level,Nodes)
As
(
    Select FirstVertex, SecondVertex, Weight, 0 As Level,CONVERT(varchar(8000),':' + FirstVertex + ':' + SecondVertex + ':')
    From #graph
    Where FirstVertex='A'

    Union all

    Select a.FirstVertex, a.SecondVertex, a.Weight, b.Level+1,b.Nodes + ':' + a.SecondVertex  + ':'
    From #graph a 
    Inner Join GraphRecursion b
    On a.FirstVertex=b.SecondVertex --And b.Level<=1
    where not b.Nodes like '%:' + a.SecondVertex + ':%'
)
Select * From GraphRecursion;

Если вы хотите избежать повторного пересечения ребра, а не повторного посещения вершины, вы должны создать свои ссылки, например. ':' + FirstVertex + '@' + SecondVertex + ':'. В этих примерах я просто использую ':' и '@' как символы, которые не появляются в именах вершин. (Избегать повторного прохождения - ближе к результатам с b.Level <= 1, но не совсем): </p> 

With GraphRecursion (FirstVertex, SecondVertex, Weight, Level,Nodes)
As
(
    Select FirstVertex, SecondVertex, Weight, 0 As Level,CONVERT(varchar(8000),':' + FirstVertex + '@' + SecondVertex + ':')
    From #graph
    Where FirstVertex='A'

    Union all

    Select a.FirstVertex, a.SecondVertex, a.Weight, b.Level+1,b.Nodes + ':' + a.FirstVertex + '@' + a.SecondVertex  + ':'
    From #graph a 
    Inner Join GraphRecursion b
    On a.FirstVertex=b.SecondVertex --And b.Level<=1
    where not b.Nodes like '%:' + a.FirstVertex + '@' + a.SecondVertex + ':%'
)

(Обратите внимание, что исходная версия b.Level <= 1 получает 5 строк из этого образца, а не четыре из моего второго примера выше). Но я верю, что это правильно. Версия b.Level <= 1 возвращает строку уровня 2 для a-> c, c-> a, a-> c, что, я думаю, нам не нужно

...