Posted on by aeinbu

Traverse a hierarchical structure with LINQ-to-Hierarchical

RecentIy I needed to find a specific TreeNode in a TreeView control. I expected that would be easy with LINQ, but quickly realized that there is no method in the .NET framework that will let me traverse all nodes of a hierarchy. I decided to create one myself.

I started by trying out how I would expect to use it. I quickly landed on a syntax like this:

var q = from node in root.FlattenHierarchy()
        select node;

How would the hierarchy be flattened? Well, implemented as an extension method, the method would look like this:

public static class LinqToHierarchical
{
    public static IEnumerable FlattenHierarchy(this TreeNode node)
    {
        yield return node;
        if(node.Nodes != null)
        {
            foreach(var child in node.Nodes)
            {
                foreach(var childOrDescendant in child.FlattenHierarchy())
                {
                    yield return childOrDescendant;
                }
            }
        }
    }
}

The above code works, and there are no problems with it if you know beforehand what kind of hierarchy you’re going to work with. In the code above, it works well with the nodes of a Windows Forms TreeView control.

Yet still, I’m not satisfied. Can I make a generic extension method that will flatten any hierarchy? Even those not made up of TreeNode objects?

To do that, we need to analyze which parts of the method needs to be swapped out. That would be the TreeNode’s Nodes property. Can we acccess that in an other way? Yes, I think a delegate can help us, so lets give it a try:

public static IEnumerable FlattenHierarchy(this T node, Func<T, IEnumerable> getChildEnumerator)
{
    yield return node;
    if(getChildEnumerator(node) != null)
    {
        foreach(var child in getChildEnumerator(node))
        {
            foreach(var childOrDescendant in child.FlattenHierarchy(getChildEnumerator))
            {
                yield return childOrDescendant;
            }
        }
    }
}

Now, that wasn’t difficult. But did we just complicate the usage of our extension method? Yes, we did. When we’re going to flatten a hierarchy, we’ll have to tell where to find the children. Not to hard though, since we can use a lambda expression for that. Here’s how we use it now:

var q = from node in root.FlattenHierarchy(x => x.Nodes)
        select node;

Now we’re able to use it with any hierarchy. Some samples include:

//The filesystem
var q = from directory in new DirectoryInfo(@"c:\").FlattenHierarchy(x => x.GetDirectories())
        select directory;
 
//XML (Yeah, I know: xml.Descendants() will also flatten this...)
var xml = XElement.Load(@"filename.xml");
var q = from element in xml.FlattenHierarchy(x => x.Elements())
        select element;
 
//Control tree in Windows Forms or in ASP.NET
var q = from control in Controls.FlattenHierarchy(x => x.Controls)
        select control;

Now, where can you go from here? I think what we have here is quite usefull as is, but some ideas include;

  • Limit traversal on depth level
  • Include leaf nodes of types that don’t include a subnode collection
  • Traverse one level at a time, instead of traversing down each branch as we find them

10 Replies to “Traverse a hierarchical structure with LINQ-to-Hierarchical”

  1. Pingback: C# alternative for Ruby’s acts_as_tree, part 2 • Onderweg Blog

  2. Converted to vb.net…

    Imports System.Runtime.CompilerServices
    Imports System.IO

    Public Class Form1

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

    Dim ctrls = From ctrl In CType(Me, Control).FlattenHierarchy(Function(x As Control) x.Controls.Cast(Of Control)())
    Select ctrl

    Dim directories = From directory In New DirectoryInfo(“C:\temp”).FlattenHierarchy(Function(x As DirectoryInfo) x.GetDirectories())
    Select directory.FullName

    End Sub
    End Class

    Module X
    _
    Public Function FlattenHierarchy(Of T)(ByVal node As T, ByVal getChildEnumerator As System.Func(Of T, IEnumerable(Of T))) As IEnumerable(Of T)
    Dim q As New List(Of T) From {node}
    Dim children As IEnumerable(Of T) = getChildEnumerator(node)

    If children IsNot Nothing Then
    For Each child As T In children
    For Each childOrDescendant In child.FlattenHierarchy(getChildEnumerator)
    q.Add(childOrDescendant)
    Next
    Next
    End If

    Return q
    End Function
    End Module

  3. What I cant find is a way to traverse a tree with a “Next” and “Previous” button.

    I can do it to a certian degree, but it has problems.

    The problem occurs when you step into a child. For example.

    +MyDVDs
    –Awaydays
    –Dog Days
    –Die Hard Series
    —-Die Hard 1
    —-Die Hard 2
    —-Die Hard 3
    –Get Smart
    –Happy Gilmore

    How can I click “Next” and have it traverse down the tree, one step at a time, and then at any point, traverse back up the tree?

    Please help.

  4. I should have given the additional level of the drive. It is the drive level that really complicates things:

    E:\DVDs
    –Awaydays
    –Dog Days
    –Die Hard Series
    —-Die Hard 1
    —-Die Hard 2
    —-Die Hard 3
    –Get Smart
    –Happy Gilmore
    F:\DVDs

    I have tried using a recursive call down the tree and storing that in a List(of T), but the problem comes in trying to assign the Selected method to the List…

    TreeView1.Selected = t_myDVDs.MovieName

    Should I store a List(of Nodes) perhaps?

    By traversing the List instead of the tree, it would seem to make the “Previous” trip back up the tree less complicated, yes?

    Please help. I have been fighting this for days.

    1. Hi Gary!

      Putting the results in a list, would allow you to walk to next or previous node with the indexer. But part of your problem is that you don’t have the depth/level of the original node.

      Well, this article is really about flattening the hierarchy, so any information about depth or level in the hierarchy will be lost.

      You can however modify my code, and add a level counter mechanism to it. The steps would be something like this:
      1. Take in an aditional parameter to the FlattenHierarchy method. (int depth)
      2. On both yield return statements you could return a new object that has both the depth+1 and the data to return.
      3. Modify the calls to the FlattenHierarchy method to include current depth.

      Hope this helps you on your way!

  5. Yes, the problem for the way I am doing it now is not knowing until runtime how deep the levels go.

    I was a “C” programmer for more than a decade but have become much more comfortable using VB.net.

    I like the idea of having recursive calls because then I dont have to code for each level, but am struggling with your suggestion of how to return the depth.

    Would it be just add one to the current depth on each return?

    Could you post a little snippet (in vb 2010) of how that would be done?

    I am really intrigued by your concept of flatting the hiearachy. Seems much more elegant than the way I am doing it now but keeping track of which level I am in and reading the next node to see if there are any children. The way I am doing it now, I have to know ahead of time how many levels to program for. Ugh…

    Any futher help would be very much appreciated.

    1. Hi Gary!

      I did your homework (in C#) ;) I made a new class LevelAndData, which is used both internally in the new FlattenHierarchyWithLevels method and as the return type.

      I think this does what you ask:

      public static class LinqToHierarchical
{
	public class LevelAndData<T>
	{
		public int Level { get; set; }
		public T Data { get; set; }
	}
 
	public static IEnumerable<LevelAndData<T>> FlattenHierarchyWithLevel<T>(this T node, Func<T, IEnumerable<T>> getChildEnumerator)
	{
		yield return new LevelAndData<T> {Level = 1, Data = node};
		if (getChildEnumerator(node) != null)
		{
			foreach (var child in getChildEnumerator(node))
			{
				foreach (var childOrDescendant in child.FlattenHierarchyWithLevel(getChildEnumerator))
				{
					yield return new LevelAndData<T>{ Level = childOrDescendant.Level+1, Data = childOrDescendant.Data};
				}
			}
		}
	}
}

      Here’s how to use it:

      class Program
{
	private static void Main(string[] args)
	{
		var q = from directory in new DirectoryInfo(@"c:")
					.FlattenHierarchyWithLevel(x => x.GetDirectories())
				select directory;
 
		foreach (var levelAndData in q.Take(10))
		{
			Console.WriteLine(levelAndData.Level + " - " + levelAndData.Data.Name);
		}
 
		Console.WriteLine("nPress ENTER...");
		Console.ReadLine();
	}
}

      You’ll need to VB-ify it yourself. Hope it helps!

  6. How can you use it with the Controls collection of the System.Web.UI.Control class?

    It does not expose an sub-list, but the elements exposed by the Controls colection expose the Controls property.

  7. This looks pretty good. I couldn’t figure out how to work this out where the root element is not a hierarchical type. In my case a ProjectTemplate has a Folders collection and the Folder objects in the Folders collections also contain collections of folders.

    Can someone improve upon my solution as I worked it out below to make it a little more elegate(ie remove the result list from the recursive function.

    public static class ProjectTemplateExtensions
    {
    public static IEnumerable RazorTemplates(this ProjectTemplate projectTemplate)
    {
    var razorTemplates = new List();
    foreach (var folder in projectTemplate.Folders)
    {
    PopulateRazorTemplates(folder, ref razorTemplates);
    }
    }

    public static void PopulateRazorTemplates(Folder folder, ref List razorTemplates)
    {
    razorTemplates.AddRange(folder.RazorTemplates);

    foreach (var childFolder in folder.Folders)
    {
    PopulateRazorTemplates( childFolder, ref razorTemplates);
    }
    }
    }

Comments are closed.