I am using Entity Framework (version 6) to map to a recursive hierarchy and it maps nicely.
My issue is that I want to recursively get ALL child nodes of a particular node in the hierarchy.
I get the child nodes quite easily using Linq:
var recursiveList = db.ProcessHierarchyItems
.Where(x => x.id == id)
.SelectMany(x => x.Children);
Does anybody know of a clean implementation, that will recursively get all children?
While it is possible to use a recursive method here, you can traverse this tree structure using an explicit stack instead to avoid using the stack space, which isn't always sufficient for large tree structures. Such a method is also very nice as an iterator block, and iterator blocks are much more expensive when recursive than regular methods, so this will perform better as well:
public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items,
Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<T>(items);
while(stack.Any())
{
var next = stack.Pop();
yield return next;
foreach(var child in childSelector(next))
stack.Push(child);
}
}
x => x.ChildrenIEnumerable, not an IQueryable, and as such only operates on in-memory collections. It cannot be translated into a DB query.Thanks Servy, I expanded on your code a bit to allow for iterating single items, as well as collections. I came across when looking for a way to find out if an exception or any inner exceptions were of a certain type, but this will have many uses.
Here is a fiddle with examples, test cases, etc. dotnetfiddle LinqTraversal
Just the helpers:
public static class LinqRecursiveHelper
{
/// <summary>
/// Return item and all children recursively.
/// </summary>
/// <typeparam name="T">Type of item.</typeparam>
/// <param name="item">The item to be traversed.</param>
/// <param name="childSelector">Child property selector.</param>
/// <returns></returns>
public static IEnumerable<T> Traverse<T>(this T item, Func<T, T> childSelector)
{
var stack = new Stack<T>(new T[] { item });
while (stack.Any())
{
var next = stack.Pop();
if (next != null)
{
yield return next;
stack.Push(childSelector(next));
}
}
}
/// <summary>
/// Return item and all children recursively.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="item"></param>
/// <param name="childSelector"></param>
/// <returns></returns>
public static IEnumerable<T> Traverse<T>(this T item, Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<T>(new T[] { item });
while (stack.Any())
{
var next = stack.Pop();
//if(next != null)
//{
yield return next;
foreach (var child in childSelector(next))
{
stack.Push(child);
}
//}
}
}
/// <summary>
/// Return item and all children recursively.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="items"></param>
/// <param name="childSelector"></param>
/// <returns></returns>
public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items,
Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<T>(items);
while (stack.Any())
{
var next = stack.Pop();
yield return next;
foreach (var child in childSelector(next))
stack.Push(child);
}
}
}
Try this. While other answers enumerate the enumerable while building the enumerable, we should consider building it without enumerating it.
public static IEnumerable<T> SelectRecursively<T>(this T source, Func<T, IEnumerable<T>> selector)
{
return selector(source).SelectMany(x => x.SelectRecursively(selector).Prepend(x));
}
The simplest solution seems to introduce a recursive method. You can't get recursive just by LINQ itself:
IEnumerable<X> GetChildren(X x)
{
foreach (var rChild in x.Children.SelectMany(child => GetChildren(child)))
{
yield return rChild;
}
}
If you have lazy loading, then this should work:
var recursiveList = db.ProcessHierarchyItems
.Where(x => x.id == id)
.AsEnumerable()
.SelectMany(x => GetChildren(x));
I like more the linq way to do recursive.
public static IEnumerable<TReturn> Recursive<TItem, TReturn>(this TItem item, Func<TItem, IEnumerable<TReturn>> select, Func<TItem, IEnumerable<TItem>> recurrence)
{
return select(item).Union(recurrence(item).Recursive(select, recurrence));
}
