Tree Structure in EF Core: How to configure a self-referencing table and use it.
One of the very common questions I am getting from the .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 a 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 OnModelCreatingmethod of your DbContextclass. 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 ToTreemethod):
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…
Top comments (2)
Thanks to Gérald Barré who pointed me his nice posts related to this topic:
I am still thinking on approach which would be working for any EF data provider, not only SQL Server.
I really would love to have #IncludeRecursively in #EntityFrameworkCore instead.
Something like:
var folder = dbContext.Folders
.Include(x => x.Parent, recursively: true)
.Include(x => x.Children, recursively: true)
.ToList(); // or maybe even .ToTree() or lookup ;)