Common table expressions, how to avoid infinite recusion when traversing a graph?

Question

I have a simple weighted graph

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

Suppose this describes a family and A is the father, B is the son and C is the mother. Let's say B is studying in an university and A has bought an apartment for him. A is living with C in a house which is commonly owned, 50-50.

I want to transform the graph into a tree, starting from A: ie.

• A owns 50% of the place C is living in
• A owns 100% of the place B is living in
• C owns 50% of the place A is living in

The graph and the generated tree could be more elaborate but I hope you get the more general picture.

On SQL Server 2005 I have

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

and I'm using the following common table expression to traverse the graph, starting from '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;

This causes

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

Limiting the level of recursion by uncommenting the And b.Level<=1 gives the expected results, but that's obviously not very useful for any practical use.

Is there a way to reference the previous iterations so that in the above example edges (ie. the FirstVertex, SecondVertex pairs) would not be repeated?

Answer 1

You could build up a list of visited nodes in another column and then prevent re-visiting them in your recursion. Something like this (not sure I've picked the right columns):

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;

If you want to avoid every re-traversing an edge, rather than ever re-visiting a vertex, you'd build up your links as e.g. ':' + FirstVertex + '@' + SecondVertex + ':'. In these examples, I'm just using ':' and '@' as characters that don't appear in vertex names. (Avoiding re-traversal - closer to results with b.Level <= 1, but not quite):

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 + ':%'
)

(Note that the original b.Level <= 1 version gets 5 rows from this sample, rather than the four from my second example above). But I believe it's correct. The b.Level <= 1 version returns a Level 2 row for a->c, c->a, a->c, which I don't think we want