Jak prawidłowo oznaczyć gałęzie drzewa w głębi pierwszy wyszukiwania

Question

Mam drzewa o strukturze jak ta:

 __2__3__4 
    / \__5__6 
0__1___7/__8__9 
    \\ 
    \\__10__11__12 
    \__ __ __ 
     13 14 15 

Node 1 ma czworo dzieci (2,7,10,13), węzłów 2 a 7 ma dwoje dzieci (oba dzielą węzeł 5 jako dziecko). Co próbuję zrobić, to utworzyć CTE, które zapewniają rekordy zawierające węzeł nadrzędny węzeł, w odległości od korzeni i gałęzi (lub widełki) jego zawartego w.

IF (OBJECT_ID('tempdb..#Discovered') IS NOT NULL) 
BEGIN 
    DROP TABLE #Discovered 
END 

CREATE TABLE #Discovered 
(
    ID int PRIMARY KEY NOT NULL, 
    Predecessor int NULL, 
    OrderDiscovered int 
); 

INSERT INTO #Discovered (ID, Predecessor, OrderDiscovered) 
VALUES (@nodeId, NULL, 0); 

    --loop through node connections table in a breadth first manner 
WHILE @@ROWCOUNT > 0 
BEGIN 
    INSERT INTO #Discovered (ID, Predecessor, OrderDiscovered) 
    SELECT c.node2_id 
       ,MIN(c.node1_id) 
       ,MIN(d.OrderDiscovered) + 1 

    FROM #Discovered d JOIN node_connections c ON d.ID = c.node1_id 
    WHERE c.node2_id NOT IN (SELECT ID FROM #Discovered) 
    GROUP BY c.node2_id 
END; 

SELECT * FROM #Discovered; 

WITH BacktraceCTE(Id, Predecessor, OrderDiscovered, Path, fork) 

AS 

( 

    SELECT d.ID, d.Predecessor, d.OrderDiscovered, CAST(d.ID AS varchar(MAX)), 0 

    FROM #Discovered d 

    WHERE d.Id = @itemId 


    UNION ALL    

    -- Recursive member, select all the nodes which have the previous 

    SELECT d.ID, d.Predecessor, d.OrderDiscovered, 

     CAST(cte.Path + '->' + CAST(d.ID as varchar(10)) as varchar(MAX)), 
     fork + CONVERT (Integer, ROW_NUMBER() OVER (ORDER BY d.ID)) - 1 

    FROM #Discovered d JOIN BacktraceCTE cte ON d.Predecessor = cte.ID 

)   

SELECT Predecessor as node1_id, OrderDiscovered as hop, fork, ID as node2_id, Path FROM BacktraceCTE 
ORDER BY fork, OrderDiscovered; 

Problem jest z sposób obliczania widelca. Za każdym razem, gdy CTE wraca do poprzedniego poziomu, dostępne są tylko numery wierszy i numer widełek na tym poziomie. To, co chciałbym osiągnąć to nagrania, w których każda kombinacja chmielu i widelca jest wyjątkowa.

Jednak z powyższym kodem dostanę wyniki, które mówią węzeł 2 do 5 skończyć się hop 3 widelec 1 i węzła 7 do 5 również skończyć się hop 3 widelec 1.

Oto drzewo dzięki oznaczeniom gałęzie, jak powinny one pojawić:

 __2__3__4  :0 
    / \__5__6  :1,2 
0__1___7/__8__9  :3 
    \\ 
    \\__10__11__12 :4 
    \__ __ __ 
     13 14 15 :5 

jak widać dla widelców 1 i 2 myślę, że najlepszym sposobem byłoby liczyć oddziału dwukrotnie nadając jej własny identyfikator w celu zachowania wyjątkowość połączenia chmielu i widelca.

Proszę pomóż mi dowiedzieć się, co muszę zrobić, aby to osiągnąć. Uważam, że powinno to być możliwe za pomocą CTE, ale być może jestem w błędzie, a jeśli tak, chciałbym wiedzieć, jaka byłaby lepsza metoda rozwiązania tego problemu.

EDIT Zestaw wynik wyglądałby następująco:

Poprzednika, ID, Zamówienie Wykryte, ścieżka, widelec

• null, 0, 0, 0, 0

• 0, 1, 1, 0-> 1, 0

• 1, 2, 2, 0-> 1-> 2, 0

• 2, 3, 3, 0-> 1> 2> 3 0

• 3, 4, 4, 0-> 1> 2> 3> 4, 0

• 2, 5, 3, 0-> 1> 2> 5 1

• 5, 6, 4, 0-> 1> 2> 5-> 6, 1

• 1, 7, 2, 0-> 1-> 7 2

• 7, 5, 3, 0-> 1-> 7> 5, 2

• 5, 6, 4, 0-> 1-> 7> 5-> 6 2

• 7, 8, 3, 0-> 1-> 7> 8 3

• 8, 9 4, 0-> 1-> 7> 8> 9 3

• 1, 10, 2, 0-> 1> 10 4

• 10 , 11, 3, 0-> 1-> 10-> 11, 4

• 11, 12, 4, 0-> 1-> 10-> 11-> 12, 4

• 1, 13, 2, 0-> 1> 13 5

• 13, 14, 3, 0-> 1> 13-> 14 5

• 14, 15, 4, 0-> 1-> 13-> 14-> 15, 5

Answer 1

Dobra, postaram się powstrzymać od poprawienia tej odpowiedzi. Po prostu było tak zabawnie uczyć się o kolejności sortowania VarBinary, znajdowaniu funkcji POWER, biciu CTE na siebie, ....

Szukasz czegoś podobnego:

declare @Nodes as Table (NodeId Int Identity(0,1), Name VarChar(10)) 
declare @Relations as Table (ParentNodeId Int, ChildNodeId Int, SiblingOrder Int) 
insert into @Nodes (Name) values 
-- ('0'), ('1'), ('2'), ('3'), ('4'), ('5'), ('6'), ('7'), ('8'), 
-- ('9'), ('10'), ('11'), ('12'), ('13'), ('14'), ('15') 
    ('zero'), ('one'), ('two'), ('three'), ('four'), ('five'), ('six'), ('seven'), ('eight'), 
    ('nine'), ('ten'), ('eleven'), ('twelve'), ('thirteen'), ('fourteen'), ('fifteen') 

insert into @Relations (ParentNodeId, ChildNodeId, SiblingOrder) values 
    (0, 1, 0), 
    (1, 2, 0), (1, 7, 1), (1, 10, 2), (1, 13, 3), 
    (2, 3, 0), (2, 5, 1), 
    (3, 4, 0), 
    (5, 6, 0), 
    (7, 5, 0), (7, 8, 1), 
    (8, 9, 0), 
    (10, 11, 0), 
    (11, 12, 0), 
    (13, 14, 0), 
    (14, 15, 0) 

declare @MaxSiblings as BigInt = 100 
; with 
DiGraph (NodeId, Name, Depth, ParentNodeId, Path, ForkIndex, DepthFirstOrder) 
as (
    -- Start with the root node(s). 
    select NodeId, Name, 0, Cast(NULL as Int), Cast(Name as VarChar(1024)), 
    Cast(0 as BigInt), Cast(Right('00' + Cast(0 as VarChar(2)), 2) as VarChar(128)) 
    from @Nodes 
    where not exists (select 42 from @Relations where ChildNodeId = NodeId) 
    union all 
    -- Add children one generation at a time. 
    select R.ChildNodeId, N.Name, DG.Depth + 1, R.ParentNodeId, Cast(DG.Path + ' > ' + N.Name as VarChar(1024)), 
    DG.ForkIndex + R.SiblingOrder * Power(@MaxSiblings, DG.Depth - 1), 
    Cast(DG.DepthFirstOrder + Right('00' + Cast(R.SiblingOrder as VarChar(2)), 2) as VarChar(128)) 
    from @Relations as R inner join 
     DiGraph as DG on DG.NodeId = R.ParentNodeId inner join 
     @Nodes as N on N.NodeId = R.ChildNodeId inner join 
     @Nodes as Parent on Parent.NodeId = R.ParentNodeId 
), 

DiGraphSorted (NodeId, Name, Depth, ParentNodeId, Path, ForkIndex, DepthFirstOrder, RowNumber) 
as (select *, Row_Number() over (order by DepthFirstOrder) as 'RowNumber' from DiGraph) 

select ParentNodeId, NodeId, Depth, Path, 
    (select Count(*) from DiGraphSorted as L 
    left outer join DiGraphSorted as R on R.RowNumber = L.RowNumber - 1 where 
    R.RowNumber < DG.RowNumber and L.ForkIndex <> R.ForkIndex) as 'ForkNumber' -- , '', * 
    from DiGraphSorted as DG 
    order by RowNumber