Click here to Skip to main content
11,641,717 members (57,985 online)
Click here to Skip to main content

Tagged as

Flatten a Hierarchical Collection of Objects with LINQ

, 18 Jul 2012 CPOL 24.4K 303 18
Rate this:
Please Sign up or sign in to vote.
Adding an extension method to LINQ to flatten any hierarchical collection

Introduction

Recently, I had a particular requirement in a project where I had to flatten the hierarchy of an object type with children of the same type.

For example, I have an object collection of type MyObject who have themselves a property of children MyObject of type IEnumerable<MyObject>. This property can be null, empty or contain iterations.

If we have in our database a hierarchy like this:

By performing the following LINQ query...

myObjects
         .Where(myObject => myObject.Id == 1)
         .ToList();  

...my result will be a list with the item “My Object A”. What to do if I want to obtain the item “My Object A” and all children under him, including children of children?

That's why I worked on an extension method to LINQ that allowed me to flatten an entire object structure of the same type on the same level.

Using the Code

Here is the extension method:

using System.Collections.Generic;

namespace System.Linq
{
    public static class LinqExtensions
    {
        /// <summary>
        ///   This method extends the LINQ methods to flatten a collection of 
        ///   items that have a property of children of the same type.
        /// </summary>
        /// <typeparam name = "T">Item type.</typeparam>
        /// <param name = "source">Source collection.</param>
        /// <param name = "childPropertySelector">
        ///   Child property selector delegate of each item. 
        ///   IEnumerable'T' childPropertySelector(T itemBeingFlattened)
        /// </param>
        /// <returns>Returns a one level list of elements of type T.</returns>
        public static IEnumerable<T> Flatten<T>(
            this IEnumerable<T> source,
            Func<T, IEnumerable<T>> childPropertySelector)
        {
            return source
                .Flatten((itemBeingFlattened, objectsBeingFlattened) =>
                         childPropertySelector(itemBeingFlattened));
        }

        /// <summary>
        ///   This method extends the LINQ methods to flatten a collection of 
        ///   items that have a property of children of the same type.
        /// </summary>
        /// <typeparam name = "T">Item type.</typeparam>
        /// <param name = "source">Source collection.</param>
        /// <param name = "childPropertySelector">
        ///   Child property selector delegate of each item. 
        ///   IEnumerable'T' childPropertySelector
        ///   (T itemBeingFlattened, IEnumerable'T' objectsBeingFlattened)
        /// </param>
        /// <returns>Returns a one level list of elements of type T.</returns>
        public static IEnumerable<T> Flatten<T>(
            this IEnumerable<T> source,
            Func<T, IEnumerable<T>, IEnumerable<T>> childPropertySelector)
        {
            return source
                .Concat(source
                            .Where(item => childPropertySelector(item, source) != null)
                            .SelectMany(itemBeingFlattened =>
                                        childPropertySelector(itemBeingFlattened, source)
                                            .Flatten(childPropertySelector)));
        }
    }
} 

And how to use it:

myObjects
         .Where(myObject => myObject.Id == 1)
         .Flatten(myObject => myObject.Children)
         .ToList(); 

Or this way if you have a cyclical tree (or other need):

 myObjects
         .Where(myObject => myObject.Id == 1)
         .Flatten((myObject, objectsBeingFlattened) => 
					myObject.Children.Except(objectsBeingFlattened))
         .ToList(); 

Points of Interest

This method can easily be integrated to a corporative framework. It’s very useful in cases where you have to transform a query linked to a TreeView into a simple list.

History

Thanks to Andrew Rissing, you're right.

Remove the Except from the method, give the responsibility to the child selector to manage if you suspect a cyclical tree.

Remove the Distinct and let the caller do.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Yves Vaillancourt
Architect CGI
Canada Canada
No Biography provided

You may also be interested in...

Comments and Discussions

 
GeneralVery nice article - needed to use with MenuItems that could include Separators - more Pin
SBendBuckeye10-Oct-13 9:23
memberSBendBuckeye10-Oct-13 9:23 
GeneralRe: Very nice article - needed to use with MenuItems that could include Separators - more Pin
Yves Vaillancourt22-Oct-13 0:55
memberYves Vaillancourt22-Oct-13 0:55 
GeneralMy vote of 5 Pin
Matt T Heffron18-Jul-12 15:53
memberMatt T Heffron18-Jul-12 15:53 
GeneralRe: My vote of 5 Pin
Yves Vaillancourt18-Jul-12 16:04
memberYves Vaillancourt18-Jul-12 16:04 
GeneralMy vote of 5 Pin
Brady Kelly20-May-12 3:38
memberBrady Kelly20-May-12 3:38 
GeneralRe: My vote of 5 Pin
Yves Vaillancourt20-May-12 16:45
memberYves Vaillancourt20-May-12 16:45 
QuestionIQueryable? Pin
springy763-May-12 1:53
memberspringy763-May-12 1:53 
AnswerRe: IQueryable? Pin
Yves Vaillancourt3-May-12 2:55
memberYves Vaillancourt3-May-12 2:55 
GeneralRe: IQueryable? Pin
springy763-May-12 3:54
memberspringy763-May-12 3:54 
SuggestionCode Improvement Pin
Andrew Rissing2-May-12 4:30
memberAndrew Rissing2-May-12 4:30 
It seems you can make some slight improvements on the method you provided:

  • You should be able to remove the Except from the method, unless you suspect a cyclical tree.
  • You should probably move the Distinct outside of the method used to scan through the hierarchy. Distinct is being called at each level of the hierarchy and is inefficient.

GeneralRe: Code Improvement Pin
Yves Vaillancourt2-May-12 9:09
memberYves Vaillancourt2-May-12 9:09 
GeneralMy vote of 5 Pin
Fréderic Cordier2-May-12 1:17
memberFréderic Cordier2-May-12 1:17 
GeneralRe: My vote of 5 Pin
Yves Vaillancourt2-May-12 1:22
memberYves Vaillancourt2-May-12 1:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150731.1 | Last Updated 18 Jul 2012
Article Copyright 2012 by Yves Vaillancourt
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid