How do I select recursive nested entities using LINQ to Entity

Question

I have an entity called Category and the entity contains a IEnumerable called ChildCategories. A category can have these child categories which can have it's own child categories and so on.

Say I have selected out the top level parent category, I want to get all child categories and their child categories and so on so that I have all hierarchical children of the category. I want this flatterned and returned with the initial category. I've tried creating something like

    public static IEnumerable<T> AllChildren<T>(this IEnumerable<T> items, 
        Func<T, IEnumerable<T>> children, bool includeSelf)
    {
        foreach (var item in items)
        {
            if (includeSelf)
            {
                yield return item;
            }
            if (children != null)
            {
                foreach (var a in children(item))
                {
                    yield return a;
                    children(a).AllChildren(children, false);
                }
            }
        }
    }

Which would get flatterned after using SelectMany method but havn't quite got it.

Answer 1

In his blog post Traverse a hierarchical structure with LINQ-to-Hierarchical , Arjan Einbu describes a method of flattening hierarchies for ease of querying:

Can I make a generic extension method that will flatten any hierarchy? [...]

To do that, we need to analyze which parts of the method needs to be swapped out. That would be the TreeNode’s Nodes property. Can we access that in an other way? Yes, I think a delegate can help us, so lets give it a try:

public static IEnumerable<T> FlattenHierarchy<T>(this T node, 
                             Func<T, IEnumerable<T>> getChildEnumerator)
{
    yield return node;
    if(getChildEnumerator(node) != null)
    {
        foreach(var child in getChildEnumerator(node))
        {
            foreach(var childOrDescendant 
                      in child.FlattenHierarchy(getChildEnumerator))
            {
                yield return childOrDescendant;
            }
        }
    }
}

casperOne describes this in his answer as well, along with the problems inherent in trying to traverse the hierarchy directly using LINQ.

Answer 2

You won't be able to do something like this with just LINQ alone; LINQ doesn't have any support for traversing an unknown level of nodes out-of-the-box.

Additionally, you don't have any real way of flattening the structure, the number of properties that is required is unknown (as it's tied to the tree depth, which is also unknown).

I'd recommend using iterators in C# to flatten the tree, something like this:

static IEnumerable<T> Flatten(this IEnumerable<T> source, 
    Func<T, IEnumerable<T>> childrenSelector)
{
    // Do standard error checking here.

    // Cycle through all of the items.
    foreach (T item in source)
    {
         // Yield the item.
         yield return item;

         // Yield all of the children.
         foreach (T child in childrenSelector(item).
             Flatten(childrenSelector))
         {
             // Yield the item.
             yield return child;
         }            
    }
}

Then, you can call the extension method and place the results in a List<T>; it's about as flat as you are going to get.

Note, you could very easily throw a StackOverflowException if the hierarchy is deep enough. To that end, you'd really want to use this non-recursive method:

static IEnumerable<T> Flatten(this IEnumerable<T> source, 
    Func<T, IEnumerable<T>> childSelector)
{
    // Do standard error checking here.

    // Create a stack for recursion.  Push all of the items
    // onto the stack.
    var stack = new Stack<T>(source);

    // While there are items on the stack.
    while (stack.Count > 0)
    {
        // Pop the item.
        T item = stack.Pop();

        // Yield the item.
        yield return item;

        // Push all of the children on the stack.
        foreach (T child in childSelector(item)) stack.Push(child);
    }
}

The Stack<T> instance lives on the heap and not on the call stack, so you won't run out of call stack space.

Also, you can change the Stack<T> to Queue<T> if you want different return semantics (or you can traverse through the children in different ways) if you require a certain order.

If you need a very specific order, I'd only recommend changing the ordering in the method if you have a large number of items that need to be traversed which makes calling OrderBy on the return value prohibitive.