Click here to Skip to main content
Click here to Skip to main content

Non-intrusive Tree & Graph Types

By , 4 Apr 2011
Rate this:
Please Sign up or sign in to vote.

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

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

About the Author

Adrian Alexander

United States United States
Adrian loves facilitating suave user experiences via the latest and greatest GUI technologies such as Windows 8 Metro-style apps as well as WPF. More generally, he finds joy in architecting software that is easy to comprehend and maintain. He does so by applying design patterns at the top-level, and by incessantly refactoring code at lower levels. He's always interested in hearing about opportunities for full or part-time development work. He resides in Pennsylvania but can potentially travel anywhere in the country. (Writing about himself in the third-person is Adrian's new hobby.)

Comments and Discussions

 
GeneralMy vote of 5 PinmemberJamesWittHurst12-Apr-11 19:39 
GeneralYou should also read this article, its very very good PinmvpSacha Barber5-Apr-11 2:09 
GeneralRe: You should also read this article, its very very good PinmemberAdrian Alexander6-Apr-11 6:24 
GeneralRe: You should also read this article, its very very good PinmemberAdrian Alexander13-Apr-11 18:57 
GeneralRe: You should also read this article, its very very good PinmvpSacha Barber13-Apr-11 19:58 
GeneralNice Pinmembersilverair20-May-09 11:42 
GeneralRe: Nice PinmemberAdrian Alexander26-May-09 5:00 
GeneralSample Project PinmemberTony Bermudez20-May-09 5:00 
GeneralGood PinmemberUroš Šmon20-May-09 0:49 
GeneralRe: Good PinmemberAdrian Alexander26-May-09 4:50 
GeneralExcellent idea PinmemberEmile van Gerwen27-Apr-09 23:02 
GeneralRe: Excellent idea PinmemberAdrian Alexander28-Apr-09 14:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140415.2 | Last Updated 4 Apr 2011
Article Copyright 2009 by Adrian Alexander
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid