Recursive Linq - Parent indication for child property?

Question

I have a table (let's say DataTable for this example) which has hierarchy records ( id,ParentId,IsEmergency) :

ParentId=0 means root.

So we have this :

0
|
+--- 4706606
|
+--- 4706605
|
+--- 4666762
        |
        +--- 4668461
               |
               +--- 4706607 

I'm after displaying only the those records who has parentId=0

But I want to add another logical column which states "this parent has IsEmergency=true in one of it's childs/sub childs

So I'm after

id         parentId        hasEmergencyInOneOfItsChild
-------------------------------------------------------
4706606    0                false
4706605    0                false
4666762    0                true

Question:

How can I achieve it via recursive linq ?

For convenience I created this Datatable :

   DataTable dt = new DataTable("myTable");
   dt.Columns.Add("id", typeof (int));
   dt.Columns.Add("parentId", typeof (int));
   dt.Columns.Add("isEmergency", typeof (bool));

   DataRow row = dt.NewRow();
   row["id"] =4706606;
   row["parentId"] = 0;
   row["isEmergency"] =false;
   dt.Rows.Add(row);

       row = dt.NewRow();
   row["id"] =4706605;
   row["parentId"] = 0;
   row["isEmergency"] = false;
   dt.Rows.Add(row);

       row = dt.NewRow();
   row["id"] =4666762;
   row["parentId"] = 0;
   row["isEmergency"] =false;
   dt.Rows.Add(row);

       row = dt.NewRow();
   row["id"] =4668461;
   row["parentId"] = 4666762;
   row["isEmergency"] = false;
   dt.Rows.Add(row);

        row = dt.NewRow();
   row["id"] =4706607;
   row["parentId"] = 4668461;
   row["isEmergency"] = true;
   dt.Rows.Add(row);

I've tried something but it is pretty nasty and not efficient

Answer 1

One approach is to define a data structure that holds the relevant properties and a recursive property to determine whether it is in an isEmergency hierarchy:

internal class Node
{
    internal string Id { get; set; }
    internal IEnumerable<Node> Children { get; set; } 
    internal bool IsEmergency { get; set; }

    internal bool IsEmergencyHierarchy
    {
        get { return IsEmergency || 
                     (Children != null && Children.Any(n => n.IsEmergencyHierarchy)); }
    }
}

Then you can construct the tree like this:

// convert rows to nodes
var nodes = dt.Rows.Cast<DataRow>().Select(r => new Node
{
    Id = r["id"].ToString(),
    ParentId = r["parentId"].ToString(),
    IsEmergency = (r["isEmergency"] as bool? == true)
}).ToList();

// group and index by parent id
var grouped = nodes.GroupBy(n => n.ParentId).ToDictionary(g => g.Key);

// match up child nodes
foreach (var n in nodes)
{
    n.Children = grouped.ContainsKey(n.Id) 
        ? (IEnumerable<Node>)grouped[n.Id] 
        : new Node[0];
}

// select top nodes
var top = grouped.ContainsKey("0") 
    ? (IEnumerable<Node>)grouped["0"] 
    : new Node[0];

You can check the result like this:

foreach (var t in top)
{
    Console.WriteLine("{0} - {1}", t.Id, t.IsEmergencyHierarchy);
}

Output:

4706606 - False
4706605 - False
4666762 - True

Answer 2

Given your data:

var lookup = dt.Rows.Cast<DataRow>().Select(x => new
{
    id = (int)x["id"],
    parentId = (int)x["parentId"],
    isEmergency = (bool)x["isEmergency"],
}).ToLookup(x => x.parentId);

I build a lookup "sorted" by parentid (let's say it's a like a dictionary but with multiple values for each key)

// Taken from http://stackoverflow.com/a/21086662/613130
public static IEnumerable<T> SelectSelfDescendents<T>(IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
    foreach (var item in source)
    {
        yield return item;

        foreach (T item2 in SelectSelfDescendents(selector(item), selector))
            yield return item2;
    }
}

A recursive function to return recursively the input collection plus the descendents

var roots = lookup[0].Select(x => new
{
    x.id,
    // x.parentId // useless, it's 0
    isEmergency = SelectSelfDescendents(new[] { x }, y => lookup[y.id]).Any(y => y.isEmergency),
    childs = SelectSelfDescendents(new[] { x }, y => lookup[y.id]).ToArray()
}).ToArray();

A little Linq to handle everything :-)

lookup[0]

We start with the "root" elements (the elements that have parentId == 0)

This one

.SelectSelfDescendents(new[] { x }, y => lookup[y.id])

given an ienumerable returns the ienumerable plus all its recursive childrens.

new[] { x }

Transforms the "current" root element in a collection of a single element.

y => lookup[y.id]

This is a descendent selector: given an element it finds in the lookup all the childs that have y.id as a parent (because the lookup is by parentId)

So in the end the SelectSelfDescendents will return new[] { x } concatenated with all its "descendents"

.Any(y => y.isEmergency)

if any isEmergency is true returns true

Now, as you noticed, I'm recalculating SelectSelfDescendants twice (once for isEmergency and once for childs)... In truth childs was a property I had added to "debug" the recursive enumeration, so it can be removed if it is not necessary. If you want to keep it, you can use the let keyword (or "expand" the let keyword as you've shown you did in chat... it is the same thing). Note that I "cache" the SelectSelfDescendents with a .ToArray() (as you did). Without it, it would still be evaluated twice, because it returns an IEnumerable<>

var roots = (from x in lookup[0]
             let childs = SelectSelfDescendents(new[] { x }, y => lookup[y.id]).ToArray()
             select new
             {
                 x.id,
                 // x.parentId // useless, it's 0
                 isEmergency = childs.Any(y => y.isEmergency),
                 childs 
             }).ToArray();