Quite often I deal with tree structures where each node can contains a set of children nodes. When is time to cycle through all the nodes, to execute some logic, you need to write a standard recursive function, an operation that is quite boring and repetitive. The question is, is it possible to write a LINQ function called Flatten() that permits you to flatten down a tree of arbitrary depth down to an IEnumerable<T>? The answer is yes.
1: public static IEnumerable<T> Flatten<T>(
2: this T root,
3: Func<T, IEnumerable<T>> getChildernFunc)
4: {
5: yield return root;
6:
7: IEnumerable<T> descendants = getChildernFunc(root);
8: if (descendants != null)
9: foreach (T element in descendants)
10: {
11: foreach (T elementinner in element.Flatten(getChildernFunc))
12: {
13: yield return elementinner;
14: }
15: }
16: }
It is amazing how simple is writing such a function with the yield return keyword. The code is based on an extension method that accepts an element of type T and a function that is capable to take an element of type T and return its childrens. Inside the body of the function I simply return the root as first, then I iterate on all childrens and for each one recursively call the Flatten function.
How easy. The code probably is not optimum for performance, but it is simple, and I always follow the rule of the three M, Measure Measure Measure, so I do not care for performance problems right now. Now I can write this simple test
1: [Test]
2: public void TestRecursivePopulationThreeLevel()
3: {
4: Recursive r1 = new Recursive(1,
5: new Recursive(2,
6: new Recursive(4)),
7: new Recursive(3));
8: var flatten = r1.Flatten(r => r.Recursives);
9: flatten.Count().Should().Be.EqualTo(4);
10: flatten.Select(r => r.Id).Should().Have.SameSequenceAs(new [] {1, 2, 4, 3});
11: }
To verify that the code really flatten down the tree. Thanks to Extension Method and yield keyword you can write a simple function that flatten down a hierarchy with fews lines of code.
Alk.
April 1st, 2011 at 3:14 pm
Hi,
Thanks for this helpful post.
I am trying to test your code, but I don’t know how Recursive class looks like. Is it possible for you to help me , or give a completely working example.
Thanks
April 1st, 2011 at 3:59 pm
Nicely done. Although anytime you see a foreach nested in a foreach it *may* be an indicator of a SelectMany operation. I rewrote your extension method and used your same test to prove the results were the same. Here is the new method:
public static IEnumerable Flatten(this T root, Func<T, IEnumerable> selector)
{
return new [] {root}.Concat(selector(root).SelectMany(x => Flatten(x, selector)));
}
April 1st, 2011 at 4:04 pm
Updated to take into consideration a null coming back from the selector.
public static IEnumerable Flatten(this T root, Func<T, IEnumerable> selector)
{
return new [] {root}.Concat((selector(root) ?? new T[0]).SelectMany(x => Flatten(x, selector)));
}
April 1st, 2011 at 4:27 pm
@kourosh
private class Recursive
{
public Int32 Id { get; set; }
public List Recursives { get; set; }
public Recursive()
{
}
public Recursive(Int32 id, params Recursive[] recursives)(recursives);
cool.
{
Id = id;
Recursives = new List
}
}
@jordan: thanks, with SelectMany you got a single line method
April 5th, 2011 at 11:25 am
Hi.
Colin Eberhardt once published an article with another approach to the same problem. http://www.codeproject.com/KB/linq/LinqToTree.aspx
I for one like that way of querying a tree better, cause it leaves the tree what it really is – a tree.
Best, Robert.
April 5th, 2011 at 1:43 pm
Yes, but I really need a function to “flatten” the tree. I have a lot of piece of code where I’m interested in the tree structure, and other ones where I’m only interested in scanning all elements of the tree, without any need to maintain the tree structure, this is where the Flatten() function is used
.
Thanks for sharing the link, the article is indeed interesting.
April 5th, 2011 at 11:37 pm
Some years ago I wrote a method to iterate recursively on any tree:
http://goo.gl/5fwxA
The “single line method” is funny!
April 6th, 2011 at 7:57 am
It is interesting to notice that trees, are one of the oldest data structures, but there is still so much interest and things to learn