クエリの結果をユニークなセットに分割する

Question

2つのエンティティ間の関係を直接的または間接的に表す2つの列を返すクエリがあります。たとえば、右側のグラフに表示されるリレーションシップは、右テーブル：

| From | To |   1 3 4 
|------|----|   o----o----o 
| 1 | 3 |   /\ 
| 1 | 4 |   / \ 
| 1 | 5 |   2 o  o 5 
| 2 | 3 |      
| 2 | 4 | 
| 2 | 5 | 
| 3 | 4 |   6 7 
| 3 | 5 |   o----o 
| 6 | 7 | 

私は何をしたいグループは、関係（上記の例ではSO 2セット）によって記載異なるグラフの数に等しくセットの数、にこのデータです。

このグループは、データベースクエリ（T-SQL）の一部として、またはデータがメモリ（C＃）に格納されると発生する可能性があります。

Answer 1

これはきれいではないかもしれませんが、これは頂点を適切にグループ化し、エッジを開始点として必要とします。エッジの頂点の順序は関係ありません。

-- Sample data. 
declare @Edges as Table (Vertex1 Int, Vertex2 Int); 
insert into @Edges (Vertex1, Vertex2) values 
    (1, 3), (3, 4), (3, 2), (3, 5), 
    (6, 7); 
select * from @Edges; 

-- Create a working table that assigns each vertex to a unique "set". 
declare @Sets as Table (SetId Int, Vertex Int); 
insert into @Sets (SetId, Vertex) 
    select Row_Number() over (order by Vertex), Vertex from (
    select distinct Vertex1 as Vertex from @Edges 
    union 
    select distinct Vertex2 from @Edges) as PH; 
select * from @Sets; 

-- Update the working table to group vertexes into sets: 
-- For each vertex update the SetId to the minimum SetId of all of the vertexes one edge away. 
-- Repeat until nothing changes. 
declare @UpdatedRows as Int = 42; 
while @UpdatedRows > 0 
    begin 
    update NS 
    set SetId = MinSetId 
    from (
     select S.SetId, S.Vertex, 
     (select Min(SetId) from @Sets where Vertex in (
      select S.Vertex union 
      select Vertex1 from @Edges where Vertex2 = S.Vertex union 
      select Vertex2 from @Edges where Vertex1 = S.Vertex) 
     ) as MinSetId 
     from @Sets as S) as NS 
    where SetId != MinSetId; 
    set @UpdatedRows = @@RowCount; 
    select * from @Sets; -- Show the work as it progresses. 
    end 

    -- The SetId values can be collapsed using Dense_Rank . 
    select Dense_Rank() over (order by SetId) as SetId, Vertex 
    from @Sets;