3

単純な加重グラフがあります

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

これが家族を表し、Aが父親、Bが息子、Cが母親であるとします。Bが大学で勉強していて、Aが彼のためにアパートを購入したとしましょう。AはCと一緒に、50-50の一般所有の家に住んでいます。

Aから始めて、グラフをツリーに変換したいと思います。

  • AはCが住んでいる場所の50％を所有しています
  • AはBが住んでいる場所の100％を所有しています
  • CはAが住んでいる場所の50％を所有しています

グラフと生成されたツリーはより複雑になる可能性がありますが、より一般的な図が得られることを願っています。

SQLServer2005では

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のペア）が繰り返されないように、前の反復を参照する方法はありますか？

4

1 に答える 1

3

別の列に訪問したノードのリストを作成し、再帰でそれらを再訪問しないようにすることができます。このようなもの（正しい列を選択したかどうかはわかりません）：

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の結果に近いが、完全ではない）：

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バージョンは、上記の2番目の例の4行ではなく、このサンプルから5行を取得することに注意してください）。しかし、私はそれが正しいと信じています。b.Level <= 1バージョンは、a-> c、c-> a、a-> cのレベル2行を返しますが、これは必要ないと思います

于 2010-03-05T07:55:56.193 に答える