Cómo etiquetar adecuadamente las ramas de un árbol en una primera búsqueda en profundidad

Question

Tengo un árbol con una estructura como esta:

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

nodo 1 tiene cuatro hijos (2,7,10,13), los nodos 2 y 7 tienen dos hijos cada uno (ambos comparten el nodo 5 como un niño). Lo que estoy tratando de hacer es crear un CET que proporcionan los registros que contienen el nodo padre, el nodo, la distancia de la raíz y la rama (o tenedor) su contenido en.

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; 

El problema es con cómo se calcula el tenedor Cada vez que el CTE vuelve a un nivel anterior, solo tiene disponibles los números de fila y cuál era el número de horquilla en ese nivel. Lo que me gustaría lograr es registros en los que cada combinación de salto y tenedor sea única.

Sin embargo, con el código anterior voy a conseguir los resultados que dicen nodo 2 a 5 terminan siendo hop 3 tenedor 1 y el nodo 7 a 5 también terminar siendo hop 3 tenedor 1.

Aquí está el árbol de nuevo con el etiquetado de las ramas con la forma en que deben aparecer:

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

Como se puede ver por las horquillas 1 y 2, creo que el mejor método sería contar la rama dos veces dándole su propio identificador de este modo preservar la unicidad de la combinación de hop y tenedor.

Por favor, ayúdame a averiguar qué debo hacer para lograr esto. Siento que esto debería ser posible con un CTE, pero quizás estoy equivocado y, si lo fuera, me encantaría saber cuál sería el mejor método para abordarlo.

EDITAR El conjunto de resultados se vería así:

predecesor, ID, Orden Descubierto, Camino, Tenedor

• nula, 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

Está bien, voy a tratar de abstenerse de ajustar esta respuesta de nuevo. Ha sido muy divertido aprender sobre el orden de VarBinary, encontrar la función de ENCENDIDO, los CTE que se golpean entre sí, ...

¿Está buscando algo como:

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