Come è possibile ordinare una gerarchia di oggetti per livello di profondità utilizzando LINQ?

Question

Considerate questa gerarchia

     A 
        | 
     -------------------------- 
     |      | 
     B      C 
     |      | 
--------|--------   --------- 
|  |  |   |  | 
D  E  F   G  H 
|  |     |  | 
| ---------    ------- | 
| |  |    |  | | 
I J  K    L  M N 

Ogni oggetto ha una proprietà Parent e di un insieme di elementi per i choldren, così per esempio, E ha un genitore di B, N di H, ecc A ha un valore null per il genitore. B.Items contiene D-F, ecc.

Che cos'è un'istruzione LINQ che posso ordinare in base al loro livello? Non mi interessa il tipo di ordinamento all'interno di un livello (cioè l'ordine di DH non importa, ma devono venire dopo B e C che devono venire dopo A.

L'unico modo in cui posso pensare è due dichiarazioni LINQ separate:

1. Eseguire un aggregato su questo, il calcolo e la memorizzazione dei livelli, come si va
2. Eseguire una seconda query LINQ sui risultati ordinazione dal Livello

B è facile, naturalmente. È una cosa con cui sto lottando, posso farlo naturalmente, ma io devo pensare che questo può essere ridotto a una dichiarazione LINQ.

Answer 1

Lei non ha specificato qual è l'obiettivo della tua ricerca, quindi non ci sono più risposte corrette:

1. LINQ to SQL o LINQ to Entities - supporto per le query ricorsive non esiste, in modo da' D ha dovuto caricare i dati in memoria ed eseguire query LINQ to Objects oppure utilizzare una stored procedure nel database (molto probabilmente utilizzando Common Table Expression). È inoltre possibile preparare una VISTA nel database e associarla al modello EF.

2. LINQ to Objects è più adatto per il lavoro, ma IMO sei ancora meglio con un metodo semplice che calcola la profondità:

   public static int GetDepth(Item item) 
   { 
       int d = 0; 
       while ((item = item.Parent) != null) 
        d++; 
       return d; 
   } 
   

   e la query è super semplice in seguito

   var results = from item in data 
          let depth = GetDepth(item) 
          orderby depth descending 
          select item; 
   

   Sarebbe facile scrivere solo una query LINQ su oggetti se la struttura dei dati era diversa e Parent aveva collegamenti a tutti i bambini. In tal caso, l'interrogazione dei dati è più semplice, poiché ogni articolo ha una raccolta di elementi dipendenti e LINQ funziona bene con le raccolte, in opposizione a singoli elementi, come la proprietà Parent. Ho scritto un post sul blog su querying hierarchy of objects using LINQ qualche tempo fa, potresti trovarlo interessante.

Answer 2

Esistono alcuni metodi per risolvere questo problema.

Innanzitutto, è possibile implementare il metodo, ad es. AsFlattenEnumerable. Imaging, si ha la classe Tree<T> che ha i dati del nodo di tipo T.

classe Declare Flatten<T>:

public Flatten<T> 
{ 
    public T Data { get; } 

    public int Level { get; } 
} 

quindi implementare AsFlattenEnumerable:

public class Tree<T> 
{ 
. . . 
    public IEnumerable<Flatten<T>> AsFlattenEnumerable() 
    { 
     . . . 
    } 

. . . 
} 

Ora è possibile ordinare i nodi con una semplice query LINQ:

var ordereNodes = from node in tree.AsFlattenEnumerable() 
        // F.e. first Level, then A, then B 
        order node by new { node.Level, node.Data.A, node.Data.B }; 

In secondo luogo, compilatore C# consente dichiarare i propri metodi per lo order by clausola (e il metodo , ovviamente).

Imaging, si dispone di una classe Tree<T> che implementa un'interfaccia ITreeEnumerable<T> (c'è un'interfaccia gerarchica simile nell'assieme System.Web).

Poi si potrebbe definire i propri metodi di estensione come Where e OrderBy:

public static ITreeEnumerable<TSource> OrderBy<TSource, TKey>(this ITreeEnumerable<TSource> source, Func<TSource, TKey> keySelector) 
{ 
    . . . 
} 

Ora è possibile ordinare i enumerables con LINQ:

var orderedNodes = from node in tree // tree implements ITreeEnumerable<T> 
        // First Level (by default), then custom ordering by A and B 
        order by new { node.A, node.B }; 
. . . 
var enumerableNodes = orderedNodes.AsEnumerable(); 

Il compilatore C# converte questa espressione:

var result = from i in obj 
      order i by i.Foo; 

a questo:

var result = obj.OrderBy(i => i.Key); 

La variabile obj lattina da di qualsiasi tipo, non necessariamente IEnumerable. Il tipo di obj dovrebbe avere il metodo o è possibile implementare il metodo di estensione.

Answer 3

Anche se i miei amici hanno inviato alcune buone risposte, sono pronto a fornire un'altra risposta. Se è possibile modificare la struttura del nodo per prestazioni migliori, è possibile impostare la proprietà depth per ogni nodo una volta e quindi ordinarli in base alla proprietà depth.

public class Node 
{ 
    public Node() 
    { 
     this.Items = new List<Node>(); 
     this.Parent = null; 
     this.Depth = 0; 
    } 
    public Node Parent { get; set; } 
    public List<Node> Items { get; set; } 
    public int Depth { get; set; } 
} 

public void SetDepths(Node node, int depth) 
{ 
    node.Depth = depth; 
    foreach (var child in node.Items) 
     SetDepths(child, depth + 1); 
} 
public void Sort(List<Node> nodes) 
{ 
    SetDepths(nodes.Single(x => x.Parent == null), 1); 
    nodes = nodes.OrderBy(x => x.Depth).ToList(); 
} 

La funzione ricorsiva dovrebbe essere chiamato come:

SetDepths(rootNode, 1); 

che qui si chiama nel metodo di ordinamento o si furgone scegliere altri luoghi per farlo.

Answer 4

senza vergogna - si potrebbe aggiungere il mio pacchetto Nuget che ho lavorato sulla chiamata Treenumerable:

https://www.nuget.org/packages/Treenumerable

https://github.com/jasonmcboyd/Treenumerable

Tu devi implementare un'interfaccia ITreeWalker che conosce come attraversare il tuo albero (due metodi).Una volta fatto questo allora si può semplicemente fare questo:

// Pseudocode 
TreeWalker walker = new TreeWalker(); 
IEnumerable<YourType> levelOrder = walker.LevelOrderTraversal(A); 

Si ottiene anche una dozzina (di più se si contano i sovraccarichi) o in modo che altri metodi per enumerare/interrogazione di strutture ad albero. L'attuale versione - 1.2.0 - ha una buona copertura di test e sembra essere abbastanza stabile.