34

C# | .NET 4.5 | Entity Framework 5

I have a class in Entity Framework that looks like this:

public class Location
{
   public long ID {get;set;}
   public long ParentID {get;set;}
   public List<Location> Children {get;set;}
}

ID is the identifier of the location, ParentID links it to a parent, and Children contains all of the children locations of the parent location. I'm looking for some easy way, likely recursively, to get all "Location" and their children to one single List containing the Location.ID's. I'm having trouble conceptualizing this recursively. Any help is appreciated.

This is what I have so far, its an extension to the entity class, but I believe it could be done better/simpler:

public List<Location> GetAllDescendants()
{
    List<Location> returnList = new List<Location>();
    List<Location> result = new List<Location>();
    result.AddRange(GetAllDescendants(this, returnList));
    return result;
}

public List<Location> GetAllDescendants(Location oID, ICollection<Location> list)
{
    list.Add(oID);
    foreach (Location o in oID.Children)
    {
            if (o.ID != oID.ID)
                    GetAllDescendants(o, list);
    }
    return list.ToList();
}

UPDATED

I ended up writing the recursion in SQL, throwing that in a SP, and then pulling that into Entity. Seemed cleaner and easier to me than using Linq, and judging by the comments Linq and Entity don't seem the best route to go. Thanks for all of the help!

5
  • Entity Framework DOES NOT contain anything to do with recursive queries.
    – Aron
    Commented Oct 8, 2013 at 2:05
  • Yes, I was looking to extend this functionality, see my edits.
    – Will
    Commented Oct 8, 2013 at 2:14
  • I assumed you wanted an Entity Framework solution rather than a Linq To Object solution backed by Entity Framework lazy loading...I looked into the Entity Framework 6 source code and wanted to actually add the functionality...however Microsoft set the relavent classes as internal. BAS$%^DS
    – Aron
    Commented Oct 8, 2013 at 2:23
  • Ended up going with recursion in SQL and referencing an SP. Thanks for the help!
    – Will
    Commented Oct 8, 2013 at 2:55
  • Related: How to flatten tree via LINQ? Commented Sep 19, 2020 at 7:58

11 Answers 11

33

You can do SelectMany

List<Location> result = myLocationList.SelectMany(x => x.Children).ToList();

You can use where condition for some selective results like

List<Location> result = myLocationList.Where(y => y.ParentID == someValue)
                                      .SelectMany(x => x.Children).ToList();

If you only required Id's of Children you can do

List<long> idResult = myLocationList.SelectMany(x => x.Children)
                                    .SelectMany(x => x.ID).ToList();
8
  • 8
    Will this traverse through multiple levels. Say if a location has children, and those children have children?
    – Will
    Commented Oct 8, 2013 at 2:11
  • +1 This is better than Syzmon's answer, and is perhaps the best you can get with EF out of the box without any database constructs. However you will still be making O(levels) database calls.
    – Aron
    Commented Oct 8, 2013 at 2:22
  • Would it be better to perhaps write this as recursive SQL and put it in a stored procedure? I'm really only looking for the ID's, not really concerned with having the whole Entity object.
    – Will
    Commented Oct 8, 2013 at 2:24
  • 1
    @Will: If you require only Id of children, look at my edited answer. Commented Oct 8, 2013 at 4:31
  • 50
    This will not recurssively get all children and grandchildren Commented Mar 19, 2014 at 5:20
16

This will do the trick:

class Extensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        var result = source.SelectMany(selector);
        if (!result.Any())
        {
            return result;
        }
        return result.Concat(result.SelectManyRecursive(selector));
    }
}

Use it like this:

List<Location> locations = new List<Location>();
//
// your code here to get locations
//
List<string> IDs = locations.SelectManyRecursive(l => l.Children).Select(l => l.ID).ToList();
4
  • 4
    If you're going to downvote, at least have the courtesy of saying why. Commented Mar 8, 2017 at 23:51
  • 3
    This will only fetch back children from below the current collection. You would need to union the source collection if you wanted those children included in the final result
    – Slicksim
    Commented Aug 16, 2018 at 11:09
  • @Slicksim not so, try again. Commented Sep 19, 2018 at 16:51
  • 1
    Downvoted because it's an inefficient solution. Calling Any, then Concat, then SelectManyRecursive to a deferred enumerable is causing multiple evaluations of the enumerable, and subsequently multiple invocations of the selector lambda. Instead of invoking the lambda once for each element in the tree, it is invoked ~3 times per element. Commented Sep 19, 2020 at 8:05
10

Try this Extension method:

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    return source.SelectMany(x => (recursion(x) != null && recursion(x).Any()) ? recursion(x).Flatten(recursion) : null)
                 .Where(x => x != null);
}

And you can use it like this:

locationList.Flatten(x => x.Children).Select(x => x.ID);
2
  • The way the code is written, you don't need the R generic parameter. Commented Mar 9, 2017 at 4:26
  • 1
    Downvoted because of multiple invocations of the recursion lambda, and multiple evaluations of the resulting enumerable. Commented Sep 19, 2020 at 8:10
10

I had no Children prop in my model, so Nikhil Agrawal's answer doesn't work for me, so here is my solution.

With following model:

public class Foo
{
    public int Id { get; set; }
    public int? ParentId { get; set; }  
    // other props
}

You can get children of one item using:

List<Foo> GetChildren(List<Foo> foos, int id)
{
    return foos
        .Where(x => x.ParentId == id)
        .Union(foos.Where(x => x.ParentId == id)
            .SelectMany(y => GetChildren(foos, y.Id))
        ).ToList();
}

For ex.

List<Foo> foos = new List<Foo>();

foos.Add(new Foo { Id = 1 });
foos.Add(new Foo { Id = 2, ParentId = 1 });
foos.Add(new Foo { Id = 3, ParentId = 2 });
foos.Add(new Foo { Id = 4 });

GetChild(foos, 1).Dump(); // will give you 2 and 3 (ids)
3
  • Perfect! I have the exact same kind of setup as your model (ID (PK), Parent ID and Child ID). This method works perfectly to get the full hierarchy of the parent ID. I knew there would be a way to do it via recursion or something but this a pure Linq example which works with EF as well! Commented Feb 9, 2022 at 12:47
  • The model in this answer is different from your original question. Commented May 1, 2022 at 13:33
  • @NikhilAgrawal yes, I already mentioned that in my answer Commented May 1, 2022 at 14:12
7

I would like to contribute my own solution, which was modified from the references below:

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    var flattened = source.ToList();

    var children = source.Select(recursion);

    if (children != null)
    {
        foreach (var child in children)
        {
            flattened.AddRange(child.Flatten(recursion));
        }
    }

    return flattened;
}

Example:

var n = new List<FamilyMember>()
{
    new FamilyMember { Name = "Dominic", Children = new List<FamilyMember>() 
        {
            new FamilyMember { Name = "Brittany", Children = new List<FamilyMember>() }
        }
    }
}.Flatten(x => x.Children).Select(x => x.Name);

Output:

  • Dominic
  • Brittany

Class:

public class FamilyMember {
    public string Name {get; set;}
    public List<FamilyMember> Children { get; set;}
}

Ref. https://stackoverflow.com/a/21054096/1477388

Note: Can't find the other reference, but someone else on SO published an answer that I copied some code from.

3
  • The way the code is written, you don't need the R generic parameter. Commented Mar 9, 2017 at 4:26
  • I don't understand how you suppose to invoke extension method child.Flatten() since child is not an IEnumerable<T> but rather just T Commented Feb 4, 2020 at 15:04
  • @CarterăVeaceslav In the example, Children will always be a list; it just may be empty. If your code works differently, then you can check the type to see if it's an IEnumerable or not i.e. return typeof(IEnumerable).IsAssignableFrom(type); Ref. stackoverflow.com/questions/28701867/… Commented Feb 4, 2020 at 17:54
6

The accepted answer from @NikhilAgrawal will not recursively get all children and grandchildren as @electricalbah has pointed out.

I do miss the answer from @EricLippert that was given on Code Review.

https://codereview.stackexchange.com/a/5661/96658

static IEnumerable<T> DepthFirstTreeTraversal<T>(T root, Func<T, IEnumerable<T>> children)      
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        // If you don't care about maintaining child order then remove the Reverse.
        foreach(var child in children(current).Reverse())
            stack.Push(child);
        yield return current;
    }
}

Called like this:

static List<Location> AllChildren(Location start)
{
    return DepthFirstTreeTraversal(start, c=>c.Children).ToList();
}

I made an example below with SelectMany. As you can see from Immediate Window you will not even get the Parent Id if you use that solution.

enter image description here

1
  • Here with a null check: var childrenOfCurrent = children(current); if (childrenOfCurrent is not null) { // If you don't care about maintaining child order then remove the Reverse. foreach (var child in childrenOfCurrent.Reverse()) stack.Push(child); } yield return current;
    – nvbnvb
    Commented Apr 27, 2022 at 11:44
5

Entity framework does not currently support recursion, and for that reason you can either

  • Rely on lazy loading child collections as you have done (beware the N+1 problem)
  • Query an arbitrary depth of objects (This will be an ugly query, though you could generate it using System.Linq.Expressions)

The only real option would be to avoid using LINQ to express the query, and instead resort to standard SQL.

Entity framework supports this scenario fairly well whether you're using code first or not.

For code-first, consider something along the lines of

var results = this.db.Database.SqlQuery<ResultType>(rawSqlQuery)

For model-first, consider using a defining query which I think is a good option as it allows further composition, or stored procedures.

To recursively get back data, you will need to understand recursive CTEs assuming you're using SQL Server, and that it is version 2005+

EDIT:

Here is the code for a recursive query to an arbitrary depth. I put this together just for fun, I doubt it would be very efficient!

var maxDepth = 5;

var query = context.Locations.Where(o => o.ID == 1);
var nextLevelQuery = query;

for (var i = 0; i < maxDepth; i++)
{
    nextLevelQuery = nextLevelQuery.SelectMany(o => o.Children);
    query = query.Concat(nextLevelQuery);
}

The flattened list is in the variable query

1
  • This is what I ended up doing. Thanks for the help.
    – Will
    Commented Oct 8, 2013 at 2:52
2

Create list to add all child using recursively public static List list = new List();

recursive funtion

 static  void GetChild(int id) // Pass parent Id
                {

                    using (var ctx =  new CodingPracticeDataSourceEntities())
                    {
                        if (ctx.Trees.Any(x => x.ParentId == id))
                        {
                            var childList = ctx.Trees.Where(x => x.ParentId == id).ToList();
                            list.AddRange(childList);
                            foreach (var item in childList)
                            {
                                GetChild(item.Id);
                            }

                        }

                    }
                }

Sample model

 public partial class Tree
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public Nullable<int> ParentId { get; set; }
    }
1

For the people who needs something generic:

/// <summary>
/// Recursively enumerate all children, grandchildren etc... in a 1-dimentional IEnumerable
/// </summary>
/// <typeparam name="TModel">The type of the model</typeparam>
/// <param name="root">The root from which to enumerate children</param>
/// <param name="childSelector">The selector on how to select the children of the root.</param>
/// <returns>A 1-dimentional IEnumerable of all it's children, grandchildren etc.. recursively.</returns>
public static IEnumerable<TModel> EnumerateChildren<TModel>(TModel root, Func<TModel, IEnumerable<TModel>> childSelector)
{
    var children = childSelector.Invoke(root);
    if (children == null)
    {
        yield break;
    }

    foreach (var child in children)
    {
        yield return child;

        foreach (var grandChild in EnumerateChildren(child, childSelector))
        {
            yield return grandChild;
        }
    }
}

Usage:

var location = GetLocation(); // Get your root.

var children = EnumerateChildren(location, l => l.Children);

0

Assuming Locations is a DbSet<Location> in your DB context, this will solve your problem "I'm looking for some easy way ... to get all 'Location' and their children to one single List containing the Location.ID's". Seems like I'm missing something, so please clarify if so.

dbContext.Locations.ToList()
// IDs only would be dbContext.Locations.Select( l => l.ID ).ToList()
0
0

This is my method for Flattening the children.

private Comment FlattenChildComments(Comment comment, ref Comment tempComment)
    {
        if (comment.ChildComments != null && comment.ChildComments.Any())
        { 
            foreach (var childComment in comment.ChildComments)
            {
                tempComment.ChildComments.Add(childComment);
                FlattenChildComments(childComment, ref tempComment);
            }
        }
        comment.ChildComments = tempComment.ChildComments;
        return comment;
    }
1
  • 5
    Don't try to edit the code away. If this isn't an answer you want to keep then delete the answer. Commented Sep 18, 2020 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.