How to search hierarchical data using Linq

Question

I need to find a tree for data that can be anywhere in the tree. How can this be done with linq?

class Program { static void Main(string[] args) { var familyRoot = new Family() {Name = "FamilyRoot"}; var familyB = new Family() {Name = "FamilyB"}; familyRoot.Children.Add(familyB); var familyC = new Family() {Name = "FamilyC"}; familyB.Children.Add(familyC); var familyD = new Family() {Name = "FamilyD"}; familyC.Children.Add(familyD); //There can be from 1 to n levels of families. //Search all children, grandchildren, great grandchildren etc, for "FamilyD" and return the object. } } public class Family { public string Name { get; set; } List<Family> _children = new List<Family>(); public List<Family> Children { get { return _children; } } } 

Answer 1

This is an extension for It'sNotALie. answer .

 public static class Linq { public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) { return selector(source).SelectMany(c => Flatten(c, selector)) .Concat(new[] { source }); } } 

An example of using the test:

 var result = familyRoot.Flatten(x => x.Children).FirstOrDefault(x => x.Name == "FamilyD"); 

Returns a familyD object.

You can make it work with the IEnumerable<T> source IEnumerable<T> :

 public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector) { return source.SelectMany(x => Flatten(x, selector)) .Concat(source); } 

Answer 2

Another solution without recursion ...

 var result = FamilyToEnumerable(familyRoot) .Where(f => f.Name == "FamilyD"); IEnumerable<Family> FamilyToEnumerable(Family f) { Stack<Family> stack = new Stack<Family>(); stack.Push(f); while (stack.Count > 0) { var family = stack.Pop(); yield return family; foreach (var child in family.Children) stack.Push(child); } } 

Answer 3

Plain:

 familyRoot.Flatten(f => f.Children); //you can do whatever you want with that sequence there. //for example you could use Where on it and find the specific families, etc. IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) { return selector(source).SelectMany(c => Flatten(selector(c), selector)) .Concat(new[]{source}); } 

Answer 4

I like when Kenneth Bo Christensen responds to using the stack, it works great, it is easy to read and fast (and it does not use recursion). The only nasty thing is that it reorders the children (because the stack is a FIFO). If the sort order does not matter to you, then this is normal. If so, sorting can be easily achieved using a selector (current). The reverse () in the foreach loop (the rest of the code is the same as in the original Kenneth post) ...

 public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) { var stack = new Stack<T>(); stack.Push(source); while (stack.Count > 0) { var current = stack.Pop(); yield return current; foreach (var child in selector(current).Reverse()) stack.Push(child); } } 

Answer 5

Well, I think that the way should go with the technique of working with hierarchical structures:

• You need an anchor to make

• You need a recursive part

   // Anchor rootFamily.Children.ForEach(childFamily => { if (childFamily.Name.Contains(search)) { // Your logic here return; } SearchForChildren(childFamily); }); // Recursion public void SearchForChildren(Family childFamily) { childFamily.Children.ForEach(_childFamily => { if (_childFamily.Name.Contains(search)) { // Your logic here return; } SearchForChildren(_childFamily); }); } 

Answer 6

So, the easiest option is to write a function that traverses your hierarchy and creates one sequence. This then happens at the beginning of your LINQ operations, for example.

  IEnumerable<T> Flatten<T>(this T source) { foreach(var item in source) { yield item; foreach(var child in Flatten(item.Children) yield child; } } 

To just call: familyRoot.Flatten (). Where (n => n.Name == "Bob");

A small alternative will give you the ability to quickly ignore an entire branch:

  IEnumerable<T> Flatten<T>(this T source, Func<T, bool> predicate) { foreach(var item in source) { if (predicate(item)) { yield item; foreach(var child in Flatten(item.Children) yield child; } } 

Then you can do things like: family.Flatten (n => n.Children.Count> 2) .Where (...)

Answer 7

I tried two of the suggested codes and made the code more clear:

  public static IEnumerable<T> Flatten1<T>(this T source, Func<T, IEnumerable<T>> selector) { return selector(source).SelectMany(c => Flatten1(c, selector)).Concat(new[] { source }); } public static IEnumerable<T> Flatten2<T>(this T source, Func<T, IEnumerable<T>> selector) { var stack = new Stack<T>(); stack.Push(source); while (stack.Count > 0) { var current = stack.Pop(); yield return current; foreach (var child in selector(current)) stack.Push(child); } } 

Flatten2 () seems a little faster, but its close.

Answer 8

Some additional answers to these questions. MarcinJuraszek and DamienG.

First, the first two give a contradictory order. To get a good tree search result, just invert the concatenation (put the “source” first).

Secondly, if you are working with an expensive source, such as EF, and want to limit entire branches, Damien's suggestion that you introduce a predicate is good and can still be done with Linq.

Finally, for an expensive source, it may also be useful to pre-select the fields of interest from each node using an injected selector.

Putting it all together:

 public static IEnumerable<R> Flatten<T,R>(this T source, Func<T, IEnumerable<T>> children , Func<T, R> selector , Func<T, bool> branchpredicate = null ) { if (children == null) throw new ArgumentNullException("children"); if (selector == null) throw new ArgumentNullException("selector"); var pred = branchpredicate ?? (src => true); if (children(source) == null) return new[] { selector(source) }; return new[] { selector(source) } .Concat(children(source) .Where(pred) .SelectMany(c => Flatten(c, children, selector, pred))); }