Using LINQ with tree structures

Question

I am using EF and Linq to return values from a database. I have a Folder structure and a folder can contain a List of Folder or a list of Device. What I want is to be able to construct a list of all Devices that sit within (or under) a folder including any folders that belong to the folder (imagine I want to see all files within a top level directory which also includes children directories).

The real kicker here is that there could be a lot of devices, so I want pagination, so ideally this would all be done with LINQ so that I can sort and paginate the query before the result set is returned.

Here is a basic version of my setup (keys, annotations and other stuff removed for simplicity)

public class Folder
{
    public virtual ICollection<Folder> Children { get; set; }
    public virtual ICollection<Device> Devices { get; set; }
}

// This is the function I currently have that only returns 1 folder
// needs to somehow be expanded to return devices for all folders beneath it too
function GetFolderDevices(int folderId, PaginationOptions options)
{
    // Get all folders and devices
    using (var dbObj = this.context.CreateDBContext())
    {
        EMDB.Models.Folder folder = dbObj
            .AddressBook
            .Include(a => a.Devices.Select(d => d.Settings))
            .FirstOrDefault(f => f.FolderId == folderId);

        // apply pagination here (already taken care of)
    }
}

Prepare view using common table expression on your database and map it into EF. — MarcinJuraszek, Aug 19 '13 at 11:06
Ho to do what? You can easily map View into EF like a table, but you have to remember it may not be possible to Insert/Update using that mapping. — MarcinJuraszek, Aug 19 '13 at 11:25
It's that bit (the view, mapping it, what it means?) that I'm unsure of :) — Chris, Aug 19 '13 at 12:01
I'd use a recursive function for that - mostly because it (in my opinion) makes the code much more readable. As far as I can tell you can do something like this: http://stackoverflow.com/questions/11830174/how-to-flatten-tree-via-linq — Ykok, Aug 19 '13 at 13:05
@Ykok Personally I prefer stuff like that, but wont that force my linq statement to execute thus bringing back all results rather than allowing me to sort / paginate on the database rather than in the C# class — Chris, Aug 19 '13 at 13:08
Yep, my bad - not reading the question properly. You should be able to use this however: http://stackoverflow.com/questions/7062882/searching-a-tree-using-linq — Ykok, Aug 19 '13 at 13:30

score 2 · Answer 1 · edited May 23 '17 at 12:23

I believe you can use an iterator. Something like this might just work:

    static IEnumerable<Folder> Descendants(Folder root)
    {
        var nodes = new Stack<Folder>(new[] { root });
        while (nodes.Any())
        {
            Folder node = nodes.Pop();
            yield return node;
            foreach (var n in node.Children) nodes.Push(n);
        }
    }

For each node yielded it will only traverse the previous nodes children.

This is basically stolen (only slightly modified) from here

I believe you could then do something like:

    // This is the function I currently have that only returns 1 folder
    // needs to somehow be expanded to return devices for all folders beneath it too
    function GetFolderDevices(int folderId, PaginationOptions options)
    {
            // Get all folders and devices
            using (var dbObj = this.context.CreateDBContext())
            {
                    EMDB.Models.Folder folder = dbObj
                            .AddressBook
                            .Include(a => a.Devices.Select(d => d.Settings))
                            .FirstOrDefault(f => f.FolderId == folderId);

                    var result = from fold in Descendants(folder)
                                 select fold;
                    // apply pagination here (already taken care of)
            }
    }

The only issue here is debugging, when you have exception other than Stack Overflow. You don't have call stack & state of local variables at each depth. For simpler logic it is readable, you are just iterating, but when you have further conditions to evaluate, it becomes difficult. How do you know depth at current iteration? Try printing tree with indention equal to depth and see how dirty code becomes. — Akash Kava, Aug 20 '13 at 09:03
The other issue I believe is that I'm totally not answering the question at hand (I wrote the above answer). This solution will still do the sorting and pagination in the C# class. Seems I'm to eager to write answers instead of reading and understanding the question - sorry. — Ykok, Aug 20 '13 at 11:32
@Ykok great that you credited me, that's some proper manners right there — vidstige, Jan 07 '16 at 19:22

Using LINQ with tree structures

1 Answers1