Non-intrusive Tree & Graph Types

Introduction

Several articles about trees have already been published on Code Project, such as [Hajek 2004], [Butler 2005], and [Chen 2006]. The code library attached to such an article usually provides a generic TreeNode<T> class that encapsulates a recursive one-to-many relationship and wraps a "data" object of type T. A TreeNode class like this will also provide enumerators and perhaps other query methods. Undoubtedly, the article will also bemoan .NET's lack of a general-purpose tree type in its standard collections library.

One such article [Hanekom 2007] that fits this description led to the NGenerics project. NGenerics provides a variety of tree and graph structures and algorithms, all implemented in .NET. It's a great project but, in my opinion, what it provides is a reference implementation. That is, its binaries are not directly usable from a real database application. The deficiency is due to the project's founding in December 2006 — long before the release of C# 3.0 in November 2007.

What about C# 3.0 is relevant, even essential, to reusable trees and graphs? To answer that question, I must first explain why I never find myself using code out-of-the-box from any of the above-mentioned articles. The short answer is simply: The Domain-Model.

The one and only responsible way to architect database applications, IMHO, involves using a domain-model. An application's domain-model consists of classes named after their counterparts in the domain being modelled (e.g. Customer, Order, FarmersDaughter, etc.) and associations between those classes. "TreeNode" describes a data-structure rather than a "real-world" object — thus it should not be part of a domain-model.

Domain-models include tree structures just fine, without help from any third-party's TreeNode class. They do so by using a List or Set type to hold their "children" collection. What has been lacking, however, is a library of general tree-related operations. An intuitive way of making such operations available for use with domain-models didn't exist until C# 3.0 came along.

Advent of Extension Methods

The essential ingredient for cooking up generalised trees and graphs, that C# 3.0 provides, is the ability to define Extension Methods. (For a succinct overview of Extension Methods' merit points for class library design, see [Wagner 2009].) Utilising a tree/graph library no longer must intrude upon the application's domain-model. Instead, the library can contain an ITreeNode interface for any domain-model class to implement. Any number of extension methods are then provided by the library, that operate on objects that implement the interface. In order to demonstrate this idea, here is the version of ITreeNode<T> from Qnomad's CoreHelpers library:

public interface ITreeNode<T> : IContainer<T,T>, IContained<T,T>
  where T : ITreeNode<T>
{
}

This interface inherits its members from two base interfaces, each of which represents a role in a aggregative association. These two interfaces can be implemented individually on different classes if the association is not recursive. ITreeNode, on the other hand, combines the two roles. When the association is recursive, then ITreeNode is implemented on a single class. Here are the two base interfaces:

public interface IContainer<TContainer, TItem>
  where TContainer : IContainer<TContainer, TItem>
  where TItem : IContained<TContainer, TItem>
{
    IList<TItem> SubItems { get; }
    bool HasSubItems { get; }
}

public interface IContained<TContainer, TItem>
  where TContainer : IContainer<TContainer, TItem>
  where TItem : IContained<TContainer, TItem>
{
    TContainer Parent { get; }
}

Now here are two methods in the library's ITreeNodeExtensions class:

public static class ITreeNodeExtensions {

    /// <summary>
    /// Is this an ancestor of the given node?
    /// </summary>
    /// <param name="maybeDescendant">
    ///   A possible descendant of this node</param>
    /// <returns>Returns true if maybeDescendant, or
    ///   any of its ancestors, are equal to this node
    /// </returns>
    public static bool IsAncestorOf<T>( this ITreeNode<T> maybeAncestor,
      ITreeNode<T> maybeDescendant ) where T : ITreeNode<T> {
        if ( maybeDescendant == maybeAncestor )
            return true; //target found!
        else if ( maybeDescendant.Parent == null )
            return false; //target not found & nowhere left to look
        else //target not found, so progress towards tree root:
            return maybeAncestor.IsAncestorOf( maybeDescendant.Parent );
    }

    /// <summary>
    /// Returns an iterator that performs a breadth-first traversal of nodes.
    /// [Source: Generic Tree in C# (www.codeproject.com/KB/recipes/phSharpTree.aspx)]
    /// </summary>
    public static IEnumerable<T> BreadthFirstNodeEnumerator<T>(
      this ITreeNode<T> root ) where T : ITreeNode<T> {
        var todo = new Queue<T>();
        todo.Enqueue( (T)root );
        while ( todo.Count > 0 ) {
            T node = todo.Dequeue();
            if ( node.HasSubItems ) {
                foreach ( T child in node.SubItems )
                    todo.Enqueue( child );
            }
            yield return node;
        }
    }
}

In order for a domain-model class to take advantage of those extension methods, it must implement ITreeNode<T> like this one does:

public class Category : ITreeNode<Category> {

    public Category() {
        SubCategories = new ObservableCollection<Category>();
    }

    private static Category root;
    private IList<Category> subCategories;
    private Category parentCategory;

    public static Category Root {
        get {
            if ( root == null ) {
                using ( IDatabaseManager dbMgr = App.CreateDbMgr() )
                    root = dbMgr.GetCategoryRoot();
            }
            return root;
        }
    }
    
    public IList<Category> SubCategories {
        get { return subCategories; }
        private set {
            subCategories = value;
            var sc = (INotifyCollectionChanged)subCategories;
            sc.CollectionChanged += new OneToManyAssocSync(
              this, "ParentCategory" ).UpdateManySide;
        }
    }

    public Category ParentCategory {
        get { return parentCategory; }
        set {
            Category oldParentCategory = parentCategory;
            parentCategory = value;
            OneToManyAssocSync.UpdateOneSide( this,
              oldParentCategory, parentCategory, "SubCategories" );
        }
    }
    
    public string Title { get; set; }

    #region ITreeNode Members

    Category IContained<Category, Category>.Parent {
        get { return ParentCategory; }
    }

    IList<Category> IContainer<Category, Category>.SubItems {
        get { return SubCategories; }
    }

    bool IContainer<Category, Category>.HasSubItems {
        get {
            return subCategories != null && subCategories.Count > 0;
        }
    }

    #endregion

    public override string ToString() {
        return GetType().Name + ": Title=\"" + Title + "\"";
    }
} 

Because the Category domain class implements ITreeNode<Category>, client code can make calls such as:

if ( categoryA.IsAncestorOf(categoryB) )
    ...

and:

foreach ( Category c in Category.Root.BreadthFirstNodeEnumerator() )
    ...

A real collections library would likely include numerous enumerators of various traversal orders and kinds, to fulfill a variety of needs. Such enumerators also allow you to take advantage of LINQ to Objects. See the "Using Extension Methods and 'LINQ to Trees'" section of [Flower 2008] for examples of this.

(If you are interested in using the OneToManyAssocSync utility class referenced in Category's source code, you can find it, too, in Qnomad's CoreHelpers library.)

Conclusion

With the release of C# 3.0 and Extension methods, the hope becomes brighter for adding reusable tree and graph types to the standard .NET collections framework.

History

• 22 April, 2009: Initial post
• 19 May, 2009: Made ITreeNode generic and updated related code
• 04 April, 2011: Added IContainer and IContained interfaces