Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to get depth of hierarchical data with linq query?

Tags:

c#

linq

I have a list of hierarchical data like this:

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

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

Note: Data in leaf of tree -->info = null

Example:

numbers are number property of Data class

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

How to know max depth of tree with linq query(Not Recursive method or for loop ) to list of data?

in this example max level is 3 for 321,322

Thanks.

like image 270
Reza ArabQaeni Avatar asked May 13 '12 09:05

Reza ArabQaeni


1 Answers

LINQ and SQL operate on flat data structures; they are not designed for recursive data structures.

With LINQ to Entities, I believe you're out of luck. Store the depth of the subtree in each node and recursively update it whenever you insert/delete a node.

With LINQ to Objects, you could define a recursive extension method that returns all paths in a tree and take the length of the longest path:

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

where

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())));
}
like image 161
dtb Avatar answered Oct 06 '22 01:10

dtb