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.

casperOne · Accepted Answer · 2016-07-26 12:20:06Z

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.

Community · Accepted Answer · 2017-05-23 12:09:11Z

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.

SolarX · Accepted Answer · 2014-12-03 06:49:49Z

0

There where some problems with casperOnes code. This works:

public static IEnumerable<T> Flatten<T>(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;
            }
        }
    }

answered Dec 3, 2014 at 6:49

SolarX

1,9632 gold badges18 silver badges26 bronze badges

1 Comment

Dude0001 Over a year ago

This should have been a comment on @caserOne's answer

Collectives™ on Stack Overflow

How do I select recursive nested entities using LINQ to Entity

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related