I’m often tasked with creating a tree representation of a structure from a flat self-referencing table. For example, in the EF extensions to Northwind, they extended the Employee table so that it has a self-referencing “ReportsTo” column. As you can see from the data below, Andrew Fuller does not report to any other employees, but Nancy, Janet, Margaret, Steven, and Laura all report to Andrew (because their ReportsTo value is the same as Andrew’s EmployeeID). Likewise Michael, Robert, and Anne all report to Steven.
In order to generate a tree representation of these records, we could start with any records that have no direct reports and then lazy load each of their children. Unfortunately for large graphs, the number of database hits will grow exponentially as we add tree levels. Typically with parent-child relationships, we could eager load the children using the DataLoadOptions with LINQ to SQL or .Includes with Entity Framework. However with self-referencing entities, this isn’t allowed. With LINQ to SQL, you will get an InvalidOperationException “Cycles not allowed in LoadOptions LoadWith type graph.”
So, how do we load the tree in one pass and build the object graphs? It’s really not that hard once you realize how reference types (classes) work in .Net. Let’s start by creating a holder for each employee and their associated direct reports:
Public Class HierarchicalEmployee
Public Sub New(emp As Employee)
Model = emp
End Sub
Public Property Model As Employee
Public Property DirectReports As New List(Of HierarchicalEmployee)
End Class
Now that we have this type, we can fill it using a simple LINQ request. In order to optimize the next step, we’ll push the values into an in-memory Dictionary indexed by the EmployeeID:
Dim allEmployees = Employees.
Select(Function(emp) New HierarchicalEmployee(emp)).
ToDictionary(Function(emp) emp.Model.EmployeeID)
Next, we iterate over the full list. For records that have a ReportsTo value, we’ll add their object pointer to their parent’s DirectReports list:
For Each emp In allEmployees.Values
If emp.Model.ReportsTo.HasValue Then
allEmployees(emp.Model.ReportsTo.Value).DirectReports.Add(emp)
End If
Next
Notice, here we take advantage of the Dictionary’s hash rather than having to iterate over the list each time we want to find the parent record. Finally, instead of returning the full list, we only return the employees that don’t have any children (where the ReportsTo is null).
Dim rootEmployees = allEmployees.Values.
Where(function(emp) Not emp.Model.ReportsTo.HasValue())
If we want to test this out in LinqPad, just use the Dump method on the resulting rootEmployees. As a result, you’ll see the following in the results pane. Notice Andrew is the only root object. He has 5 direct reports and one of his reports had 3 reports. You could just as easily bind this to a treeview control or output it using your favorite UI tooling.
The nice thing about this solution is that if we check the generated SQL, we will just see a simple (single) SQL request to generate the entire graph. As a summary, here’s the complete code from the LinqPad sample:
Sub Main
Dim allEmployees = Employees.
Select(Function(emp) New HierarchicalEmployee(emp)).
ToDictionary(Function(emp) emp.Model.EmployeeID)
For Each emp In allEmployees.Values
If emp.Model.ReportsTo.HasValue Then
allEmployees(emp.Model.ReportsTo.Value).DirectReports.Add(emp)
End If
Next
Dim rootEmployees = allEmployees.Values.
Where(function(emp) Not emp.Model.ReportsTo.HasValue())
rootEmployees.Dump
End Sub
Public Class HierarchicalEmployee
Public Sub New(emp As Employee)
Model = emp
End Sub
Public Property Model As Employee
Public Property DirectReports As New List(Of HierarchicalEmployee)
End Class
