An extension method to convert a flat collection to a Hierarchical collection

This is a report from here…

 

A while ago I posted an article about LINQ to SQL and WPF treeviews. I demonstrated how to use multiple levels in treeviews and how to group data with LINQ. One interesting subject wasn’t covered, namely self referencing tables or the adjacency list model. A WPF TreeView control does not support this. That is why I created a LINQ extension method to convert a flat collection to a hierarchical structure of nested collections which can be assigned to the ItemsSource of a WPF Treeview.

 

 

 

 

Adjacency model / self referencing table

 

Hierarchies like trees, organizational charts, … are sometimes difficult to store in database tables. The most common database pattern to store hierarchical data is known as the adjacency model. It has been introduced by the famous computer scientist Edgar Frank Codd. It’s called the “adjacency” model because a reference to the parent data is stored in the same row as the child data, in an adjacent column. These kind of tables are also called self referencing tables.

 

Let’s crystalize this by displaying the Employees table in the Northwind database.

 

EmployeeID LastName FirstName ReportsTo
1 Davolio Nancy 2
2 Fuller Andrew null
3 Leverling Janet 2
4 Peacock Margaret 2
5 Buchanan Steven 2
6 Suyama Michael 5
7 King Robert 5
8 Callahan Laura 2
9 Dodsworth Anne 5

 

In this table, the child is the same kind of row as the parent. The ReportsTo column is a foreign key referencing the EmpNo column. So each employee has a reference to his/her boss.

 

If you want to use this data in a WPF TreeView, then you have to convert the adjacency list model to a hierarchical model/nested set model. This should be the result :

 

EmployeeID LastName FirstName ReportsTo Depth
2 Fuller Andrew null 1
      1 Davolio Nancy 2 2
      3 Leverling Janet 2 2
      4 Peacock Margaret 2 2
      5 Buchanan Steven 2 2
            6 Suyama Michael 5 3
            7 King Robert 5 3
            9 Dodsworth Anne 5 3
      8 Callahan Laura 2 2

 

In SQL Server 2005 you can use CTE (Common Table Expressions) and a recursive function to query this kind of data. And SQL Server 2008, which will be released one of the next months, will provide a new SQLCLR datatype called HierarchyID which will support manipulating and querying hierarchical data. Besides these database features, I wanted to create a .NET solution which can be used to convert a flat collection to a hierarchical structure of nested collections. Next steps will describe how I implemented the LINQ AsHierarchy extension method.

 

 

 

GetEmployeesHierarchy() method

 

I first started creating a new EmployeeHierarchy class. This class contains an Employee entity (the boss) and a collection of child employees.

public class EmployeeHierarchy
{
  public Employee Employee { get; set; }
  public IEnumerable<EmployeeHierarchy> Employees { get; set; }
}

 

In .NET 3.5 we have LINQ at our’s disposal. So I created a recursive GetEmployeesHierachy function which will start with the director (who does not have to report to anyone, ReportsTo = null) and query all employees which are working for him (ReportsTo == EmployeeId of boss). This will be repeated recursively. Finally this function will return a collection of EmployeeHierarchy objects.

 

public IEnumerable<EmployeeHierarchy> GetEmployeesHierachy(IEnumerable<Employee> allEmployees, Employee parentEmployee)
{
  int? parentEmployeeId = null;

  if (parentEmployee != null)
    parentEmployeeId = parentEmployee.EmployeeID;

  var childEmployees = allEmployees.Where(e => e.ReportsTo == parentEmployeeId);

  Collection<EmployeeHierarchy> hierarchy = new Collection<EmployeeHierarchy>();

  foreach (var emp in childEmployees)
    hierarchy.Add(new EmployeeHierarchy() { Employee = emp, Employees = GetEmployeesHierachy(allEmployees, emp) });

  return hierarchy;
}

 

This function can be called after a LINQ to SQL or LINQ to Entities (Entity Framework) query. Make sure to call the ToList() extension method. It is much more performant to first load all data from the database and then convert it to a hierachical structure. By calling the ToList() method all references to the database will be removed.

 

NorthWindDataContext dc = new NorthWindDataContext();

var employeesHierarchy = GetEmployeesHierachy(dc.Employees.AsEnumerable(), null);

treeViewEmployees.ItemsSource = employeesHierarchy;

 

AsHierarchy() extension method

 

Previous routines did work fine but I wanted a more generic solution. My motto is “do more with less code” so I created a HierarchyNode<T> class and a LINQ AsHierarchy() extension method which uses generics and anonymous functions (=Func delegates). This method will return an IEnumerable collection of generic HierarchyNode<T> objects.

 

This is the source code which does all the magic. Just copy it to one of your own projects.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ScipBe.Common.LinqExtensions
{
  // Stefan Cruysberghs, http://www.scip.be, March 2008

  /// <summary>
  /// Hierarchy node class which contains a nested collection of hierarchy nodes
  /// </summary>
  /// <typeparam name="T">Entity</typeparam>
  public class HierarchyNode<T> where T : class
  {
    public T Entity { get; set; }
    public IEnumerable<HierarchyNode<T>> ChildNodes { get; set; }
    public int Depth { get; set; }
  }

  public static class LinqExtensionMethods
  {
    private static System.Collections.Generic.IEnumerable<HierarchyNode<TEntity>> CreateHierarchy<TEntity, TProperty>
      (IEnumerable<TEntity> allItems, TEntity parentItem,
      Func<TEntity, TProperty> idProperty, Func<TEntity, TProperty> parentIdProperty, int depth) where TEntity : class
    {
      IEnumerable<TEntity> childs;

      if (parentItem == null)
        childs = allItems.Where(i => parentIdProperty(i).Equals(default(TProperty)));
      else
        childs = allItems.Where(i => parentIdProperty(i).Equals(idProperty(parentItem)));

      if (childs.Count() > 0)
      {
        depth++;

        foreach (var item in childs)
          yield return new HierarchyNode<TEntity>() { Entity = item, ChildNodes = CreateHierarchy<TEntity, TProperty>
            (allItems, item, idProperty, parentIdProperty, depth), Depth = depth };
      }
    }

    /// <summary>
    /// LINQ IEnumerable AsHierachy() extension method
    /// </summary>
    /// <typeparam name="TEntity">Entity class</typeparam>
    /// <typeparam name="TProperty">Property of entity class</typeparam>
    /// <param name="allItems">Flat collection of entities</param>
    /// <param name="idProperty">Reference to Id/Key of entity</param>
    /// <param name="parentIdProperty">Reference to parent Id/Key</param>
    /// <returns>Hierarchical structure of entities</returns>
    public static System.Collections.Generic.IEnumerable<HierarchyNode<TEntity>> AsHierarchy<TEntity, TProperty>
      (this IEnumerable<TEntity> allItems, Func<TEntity, TProperty> idProperty, Func<TEntity, TProperty> parentIdProperty)
      where TEntity : class
    {
      return CreateHierarchy(allItems, default(TEntity), idProperty, parentIdProperty, 0);
    }
  }
}

AsHierarchy() examples

Call the AsHierachy() method and pass the Id/Key and the ParentId/Key of the entity as anonymous functions. As you can see, it really is that simple.

NorthWindDataContext dc = new NorthWindDataContext();

var hierachy = dc.Employees.ToList().AsHierarchy(e => e.EmployeeID, e => e.ReportsTo);

treeView1.ItemsSource = hierarchy;

 

Within each level of the hierarchical tree the original order will be preserved. So it is possible to use the LINQ OrderBy and OrderByDescending extension methods.

var hierachy = dc.Employees.OrderByDescending(e => e.LastName).ToList().
  AsHierarchy(e => e.EmployeeID, e => e.ReportsTo);

 

Of course this extension method will also work with anonymous classes.

var hierachy = (from e in dc.Employees
               select new { Id = e.EmployeeID, FullName = e.FirstName + " " + e.LastName, ParentId = e.ReportsTo }).ToList()
               AsHierarchy(e => e.Id, e => e.ParentId);

 

AsHierarchy() in LINQPad

External extension methods can also be used in LINPad. Go to Query >> Advanced Properties and add a reference to the assemby which holds the AsHierachy extension method. Don’t forget to add the name of the namespace at the tabsheet Additional Namespace Imports.

LINQPad will show you a nice representation of the hierarchical structure.

 

 

 

Display hierarchy with WPF TreeView

Binding a collection of generic HierarchyNode<T> objects to a WPF TreeView is quite easy. Just set the ItemsSource of the HierarchicalDataTemplate to ChildNodes. Now the TreeView will recursively display all HierarchyNode<T> objects. Make sure you use the fixed name Entity in the binding of the template.

<TreeView Name="treeView1">
    <TreeView.ItemTemplate>
        <HierarchicalDataTemplate ItemsSource="{Binding Path=ChildNodes}">
            <StackPanel Orientation="Horizontal">
                <TextBlock Text="{Binding Path=Entity.FirstName}"></TextBlock>
                <TextBlock Text=" "></TextBlock>
                <TextBlock Text="{Binding Path=Entity.LastName}"></TextBlock>
            </StackPanel>
        </HierarchicalDataTemplate>
    </TreeView.ItemTemplate>
</TreeView>

 

his is how the TreeView will look like :

Once you have the data in the TreeView it is up to you to give it a nice visual representation. Take a look at the Custom TreeView Layout in WPF article of Josh Smith who demonstrates how to render a TreeView as an organizational chart. I already copied his XAML example and this is how my Employees tree will be displayed :

Let’s summerize this article :

  • Copy the source of the AsHierarchy() extension method to your project
  • Add a TreeView control and define a HierarchicalDataTemplate which uses the ChildNodes and Entity properties in your XAML file
  • Call the AsHierarchy() method with the id/key and parentid/key in a LINQ to Objects, LINQ to SQL or LINQ to Entities query
  • Assign the result query to the ItemsSource of the WPF TreeView

I hope you like this LINQ extension method and that you can take advantage of this free code.

New improvements and a LINQ to SQL (IQueryable) version can be found in a more recent article.