Walking a hierarchy table with Linq

Question

I have a table with two columns, GroupId and ParentId (both are GUIDS). The table forms a hierarchy so I can look for a value in the “GroupId” filed, when I have found it I can look at its ParentId. This ParentId will also appear in the GroupId of a different record. I can use this to walk up the hierarchy tree from any point to the root (root is an empty GUID). What I’d like to do is get a list of records when I know a GroupId. This would be the record with the GroupId and all the parents back to the root record. Is this possible with Linq and if so, can anyone provide a code snippet?

Answer 1

LINQ is not designed to handle recursive selection.

It is certainly possible to write your own extension method to compensate for that in LINQ to Objects, but I've found that LINQ to Entities does not like functionality not easily translated into SQL.

Edit: Funnily enough, LINQ to Entities does not complain about Matt Warren's take on recursion using LINQ here. You could do:

var result = db.Table.Where(item => item.GroupId == 5)
                     .Traverse(item => db.Table.Where(parent 
                                                       => item.ParentId == parent.GroupId));

using the extension method defined here:

static class LinqExtensions
{
    public static IEnumerable<T> Traverse<T>(this IEnumerable<T> source,
                                             Func<T,IEnumerable<T>> selector){
    foreach(T item in source){
        yield return item;
        IEnumerable<T> children = selector(item);
        foreach (T child in children.Traverse(selector))
        {
            yield return child;
        }
    }
}

Performace might be poor, though.