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

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 uncommenti开发者_开发问答ng 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?

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