Geek Answers Handbook

How can you sort the hierarchy of objects by depth using LINQ?

Consider this hierarchy

A | -------------------------- | | BC | | --------|-------- --------- | | | | | DEFGH | | | | | --------- ------- | | | | | | | IJKLMN

Each object has the Parent property and the Items collection for choldren, therefore, for example, E has a parent B, N from H, etc. A is null for the parent. B.Items contains DF etc.

What is a LINQ statement that I can sort by their level? I don't care about the sort order within the level (i.e. the DH order does not matter, but they should come after B and C, which should appear after A.

The only way I can imagine are two separate linq expressions:

  • Run the unit over it, calculate and save levels when passing
  • Run the second LINQ query to sort the results by level.

B is easy, of course. This is A I am fighting with. Of course, I can do this procedurally, but I should think that this can be reduced to a LINQ statement.

+6
source share
4 answers

You did not indicate what the purpose of your request is, therefore there are several correct answers:

  • LINQ to SQL or LINQ to Entities - support for recursive queries does not exist, so you had to load data into memory and execute a LINQ to Objects query or use a stored procedure in a database (most likely using the Common Table expression). You can also prepare VIEW in the database and map it to your EF model.

  • LINQ to Objects is better for working, but IMO is still best for you with a simple method designed for depth:

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

    and the request will be super simple later

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

    It would be easy to write only one LINQ to Objects query if your data structure was different and the parent had references to all the children. In this case, querying the data is simpler because each element has a collection of dependent elements, and LINQ works well with collections based on individual elements, for example, your Parent property. I wrote a blogpost about querying a hierarchy of objects using LINQ some time ago, you might find it interesting.

+6
source

Although my friends posted good answers, I am ready to answer another question. If it is possible to change the structure of a node for better performance, you can set the depth property for each node once, and then sort them based on the depth property.

 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(); }

A recursive function should be called as:

 SetDepths(rootNode, 1);

which he calls here in the sorting method, or you select any other places for this.

+2
source

There are several ways to solve this problem.

Firstly, you can implement the method, i.e. AsFlattenEnumerable . Imaging, you have a Tree<T> class that has node data of type T

Declare a Flatten<T> class:

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

Then do AsFlattenEnumerable :

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

Now you can sort the nodes with a simple LINQ query:

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

Secondly, the C # compiler allows you to declare your own methods for the order by clause (and the OrderBy method, of course).

Imaging, you have a Tree<T> class that implements the ITreeEnumerable<T> interface (there is a similar hierarchical interface in the System.Web assembly).

You can then define your own extension methods, such as Where and OrderBy :

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

Now you can sort your enums using 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();

The C # compiler converts this expression:

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

:

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

The obj variable can be of any type, not necessarily IEnumerable . The obj type must have an OrderBy method, or you can implement an extension method.

0
source

Shameless plugin - you can add my Nuget package, which I worked on called Treenumerable:

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

https://github.com/jasonmcboyd/Treenumerable

You need to implement the ITreeWalker interface, which knows how to navigate your tree (two methods). Once you do this, you can simply do this:

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

You also get a dozen (more if you consider overloads) or other methods for listing / querying tree structures. The current version - 1.2.0 - has good coverage for testing and seems pretty stable.

0
source

More articles:


All Articles