Pull to refresh

Tree Structure in EF Core: How to configure a self-referencing table and use it

Reading time 4 min
Views 26K

One of the very common questions I am getting from .NET community is how to configure and use the tree structures in EF Core. This story is one of the possible ways to do it.


The common tree structures are file tree, categories hierarchy, and so on. Let it be folders tree for example. The entity class will be a Folder:


public class Folder
{
    public Guid Id { get; set; }
    public string Name { get; set; }      
    public Folder Parent { get; set; }
    public Guid? ParentId { get; set; }
    public ICollection<Folder> SubFolders { get; } = new List<Folder>();
}

This is how to configure DB schema via overriding OnModelCreating method of your DbContext class. This could be done via configuration property attributes on our entity class, but I prefer to define DB schema this way.


protected override void OnModelCreating(ModelBuilder modelBuilder)
{
    modelBuilder.Entity<Folder>(entity =>
    {
        entity.HasKey(x => x.Id);
        entity.Property(x=> x.Name);
        entity.HasOne(x=> x.Parent)
            .WithMany(x=> x.SubFolders)
            .HasForeignKey(x=> x.ParentId)
            .IsRequired(false)
            .OnDelete(DeleteBehavior.Restrict);
    });
    // ...
}

This is how to load data from DB as a tree of folders, flatten it as a plain list of folder “nodes”, and get some details related to tree structure like node level, node parents, etc.:


{
    List<Folder> all = _dbContext.Folders.Include(x => x.Parent).ToList();
    TreeExtensions.ITree<Folder> virtualRootNode = all.ToTree((parent, child) => child.ParentId == parent.Id);
    List<TreeExtensions.ITree<Folder>> rootLevelFoldersWithSubTree = virtualRootNode.Children.ToList();
    List<TreeExtensions.ITree<Folder>> flattenedListOfFolderNodes = virtualRootNode.Children.Flatten(node => node.Children).ToList();
    // Each Folder entity can be retrieved via node.Data property:
    TreeExtensions.ITree<Folder> folderNode = flattenedListOfFolderNodes.First(node => node.Data.Name == "MyFolder");
    Folder folder = folderNode.Data;
    int level = folderNode.Level;
    bool isLeaf = folderNode.IsLeaf;
    bool isRoot = folderNode.IsRoot;
    ICollection<TreeExtensions.ITree<Folder>> children = folderNode.Children;
    TreeExtensions.ITree<Folder> parent = folderNode.Parent;
    List<Folder> parents = GetParents(folderNode);
}

This method demonstrates how to get all parents from the tree for specific node:


private static List<T> GetParents<T>(TreeExtensions.ITree<T> node, List<T> parentNodes = null) where T : class
{
    while (true)
    {
        parentNodes ??= new List<T>();
        if (node?.Parent?.Data == null) return parentNodes;
        parentNodes.Add(node.Parent.Data);
        node = node.Parent;
    }
}

Tree operation extension methods below and helper interface for wrapping any entity into the tree node object. So technically your entity can be any class where you have relation parent->children (to get the plain list of nodes from the tree using Flatten) and child-> parent (to build the tree from the list using ToTree method):


public static class TreeExtensions
{
    /// <summary> Generic interface for tree node structure </summary>
    /// <typeparam name="T"></typeparam>
    public interface ITree<T>
    {
        T Data { get; }
        ITree<T> Parent { get; }
        ICollection<ITree<T>> Children { get; }
        bool IsRoot { get; }
        bool IsLeaf { get; }
        int Level { get; }
    }
    /// <summary> Flatten tree to plain list of nodes </summary>
    public static IEnumerable<TNode> Flatten<TNode>(this IEnumerable<TNode> nodes, Func<TNode, IEnumerable<TNode>> childrenSelector)
    {
        if (nodes == null) throw new ArgumentNullException(nameof(nodes));
        return nodes.SelectMany(c => childrenSelector(c).Flatten(childrenSelector)).Concat(nodes);
    }
    /// <summary> Converts given list to tree. </summary>
    /// <typeparam name="T">Custom data type to associate with tree node.</typeparam>
    /// <param name="items">The collection items.</param>
    /// <param name="parentSelector">Expression to select parent.</param>
    public static ITree<T> ToTree<T>(this IList<T> items, Func<T, T, bool> parentSelector)
    {
        if (items == null) throw new ArgumentNullException(nameof(items));
        var lookup = items.ToLookup(item => items.FirstOrDefault(parent => parentSelector(parent, item)),
            child => child);
        return Tree<T>.FromLookup(lookup);
    }
    /// <summary> Internal implementation of <see cref="ITree{T}" /></summary>
    /// <typeparam name="T">Custom data type to associate with tree node.</typeparam>
    internal class Tree<T> : ITree<T>
    {
        public T Data { get; }
        public ITree<T> Parent { get; private set; }
        public ICollection<ITree<T>> Children { get; }
        public bool IsRoot => Parent == null;
        public bool IsLeaf => Children.Count == 0;
        public int Level => IsRoot ? 0 : Parent.Level + 1;
        private Tree(T data)
        {
            Children = new LinkedList<ITree<T>>();
            Data = data;
        }
        public static Tree<T> FromLookup(ILookup<T, T> lookup)
        {
            var rootData = lookup.Count == 1 ? lookup.First().Key : default(T);
            var root = new Tree<T>(rootData);
            root.LoadChildren(lookup);
            return root;
        }
        private void LoadChildren(ILookup<T, T> lookup)
        {
            foreach (var data in lookup[Data])
            {
                var child = new Tree<T>(data) {Parent = this};
                Children.Add(child);
                child.LoadChildren(lookup);
            }
        }
    }
}

Hope that helps. Enjoy coding with the Coding Machine

Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+1
Comments 1
Comments Comments 1

Articles