¿Cómo obtener la profundidad de los datos jerárquicos con la consulta linq?

Question

tengo una lista de datos jerárquicos como esto:

var list = new List<Data>(){some data...} 

class Data 
{ 
    public int number; 
    public List<Data> info; 
} 

Nota: Los datos de la hoja del árbol ->info = null

Ejemplo:

números son number property de la clase de datos

--1 
     --11 
    --2 
     --21 
     --22 
     --23 
     --24 
    --3 
     --31 
     --32 
      --321 
      --322 
    --4 
     --41 
     --42 

Cómo saber la profundidad máxima de tr ee con consulta linq (¿Método no recursivo o para bucle) a la lista de datos?

en este ejemplo el nivel máximo es 3 para 321.322

Gracias.

Answer 1

LINQ y SQL operan en estructuras de datos planas; no están diseñados para estructuras de datos recursivas.

Con LINQ to Entities, creo que no tiene suerte. Almacene la profundidad del subárbol en cada nodo y actualícela recursivamente cada vez que inserte/elimine un nodo.

Con LINQ a objetos, se podría definir un método de extensión recursiva que devuelve todos los caminos en un árbol y tomar la longitud del camino más largo:

var result = root.Paths().Max(path => path.Length); 

donde

public static IEnumerable<Data[]> Paths(this Data data) 
{ 
    return Paths(data, new[] { data }); 
} 

private static IEnumerable<Data[]> Paths(Data data, Data[] path) 
{ 
    return new[] { path }.Concat((data.info ?? Enumerable.Empty<Data>()) 
    .SelectMany(child => Paths(child, path.Concat(new[] { child }).ToArray()))); 
} 

Answer 2

Todos los operadores LINQ utilice un bucle de alguna manera, por lo que no es posible resolver con linq si el requisito no es bucle.

Es posible sin recursion. Solo necesitas una pila. Algo así como

public static IEnumerable<Tuple<int, T>> FlattenWithDepth<T>(T root, Func<T, IEnumerable<T>> children) { 
    var stack = new Stack<Tuple<int, T>>(); 

    stack.Push(Tuple.Create(1, root)); 

    while (stack.Count > 0) { 
     var node = stack.Pop(); 

     foreach (var child in children(node.Item2)) { 
      stack.Push(Tuple.Create(node.Item1+1, child)); 
     } 
     yield return node; 
    } 
} 

Su consulta LINQ será entonces

FlattenWithDepth(root, x => x.info ?? Enumerable.Empty<Data>()).Max(x => x.Item1); 

(lo siento no tienen un compilador disponible para verificar)

** Editar. Sólo vimos que tenía múltiples raíces **

list.SelectMany(y => FlattenWithDepth(y, x => x.info ?? Enumerable.Empty<Data>())) 
    .Max(x => x.Item1) 

Answer 3

Si se debe utilizar en el PP, sugeriría añadir columna adicional a su base de datos para guardar la profundidad del árbol, hay alguna situación que los cambios de profundidad:

1. Añadiendo nuevo elemento, su profundidad es FatherDepth + 1.
2. Eliminar: Si esta es la relación de cascada no hay ningún problema con la eliminación, pero si no está en cascada se debe escribir una consulta recursiva para actualizar la profundidad de los niños.

Para encontrar la profundidad solo ejecute una consulta para encontrar el valor de profundidad máxima.

Answer 4

El siguiente funcionaría:

internal static class ListDataExtension 
{ 
    public static int MaxDepthOfTree(this List<Data> dataList) 
    { 
     return dataList.Max(data => data.MaxDepthOfTree); 
    } 
} 
internal class Data 
{ 
    public int number; 
    public List<Data> info; 

    public int MaxDepthOfTree 
    { 
     get 
     { 
      return GetDepth(1); 
     } 
    } 

    int GetDepth(int depth) 
    { 
     if (info == null) 
      return depth; 
     var maxChild = info.Max(x => x.GetDepth(depth)); 
     return maxChild + 1; 
    } 
} 

A continuación, sólo llaman:

var maxDepth = list.MaxDepthOfTree();