In this article I hope to highlight a few of the important facts about building and rendering hierarchies in your pages. I'll work through a simple, theoretical excercise then leave you with a working demo. Lets get started...

First Steps

From a high-level there's 3 steps to painting a hierarchy on a page:

• Assemble all the data that you need
• Arrange it in the right order
• Print each item underneath it's parent with a symbol or space to indent it

The first task is getting the data into a useable state. Typically members in the hierarchy will be linked via a Foreign Key; in the case of the "Boss/MiddleManager/Employee" example, the Foreign Key is likely to be a self-referencing join because all of the items will exist within the same table - "Employee", this type of hierarchy also tends to have an unlimited number of levels, i.e.:

    - Chairman
        - CEO
            - Manager
                - Middle-Manager
                    - Employee
            - Manager
                - Middle-Manager
                    - Employee

Each of these items will have a unique id (Primary Key) and a non-unique id that points to the unique id of their manager (Foreign Key).

Some Golden Rules

Before I move on, there are a couple of scalability issues that tend to arise when dealing with hierarchical data. I try to stick to the following 4 rules to help ensure that my apps don't crash too many servers ;-):

• Limit calls to the database
• Get the raw data as close to what I need from within the database
• Do any looping - i.e. recursion - in the middle-tier
• Build the simplest thing that will work!

The second point is particularly important to me. Making the most of sql joins and calculated columns means that often you will find that you can get away with a single call to the database and avoid doing a stack of rework in OnItemDataBound.

Step 1 : Getting the data

To continue on with my unlimited 'Employee' example, I'll grab a simple resultset. A query something like this should do:

    SELECT [Id], [ReportsTo], [Title], FirstName, LastName 
    FROM Employee

Resultset returned from database query

I return the results to a DataSet in the middle-tier and add a self-referencing DataRelation to represent the hierarchy in memory. I also add a column to the DataTable to keep track of depth, this can save me having to do messy operations during the actual binding operation and allows me to use that figure to calculate the width or type of image to display when presenting the data.

    
    DataTable tbl = GetData() ;
    DataSet ds = new DataSet() ;
    ds.Tables.Add( tbl ) ;

    // append a column to keep track of depth
    tbl.Columns.Add(new DataColumn("Depth", typeof(Int32))) ;

    DataRelation rel = new DataRelation(
            "ParentChild",
            tbl.Columns["Id"],
            tbl.Columns["ParentId"],
            false
        ) ;
    rel.Nested = true ;
    ds.Relations.Add( rel ) ;

    ' return the above dataset from database
    Dim tbl As DataTable = GetData() 
    Dim ds As New DataSet()
    ds.Tables.Add(tbl)

    ' append a column to keep track of depth
    tbl.Columns.Add(New DataColumn("Depth", GetType(Int32)))

    Dim rel As New DataRelation( _
            "ParentChild", _
            tbl.Columns("Id"), _
            tbl.Columns("ReportsTo"), _
            False _
        )
    rel.Nested = True
    ds.Relations.Add(rel)

I think that it's worth noting that, up until now I've done nothing terribly special. I've returned a dirt simple rowset from my datastore and used a DataRelation object to relate my data. I'll discuss the special benefits gained from using this object in a moment!

Step 2 : Arranging the data

We now have a data resultset that is hierarchically represented in memory. What I want to do is to actually compute the nesting depth of each member and get the rows into the correct order before I do my databind. To do that I'll create a temporary table which is schematically identical to my current table and use it to append correctly ordered rows:

    // configure our global table
    DataTable mTable ;
    .
    .
    .
    mTable = tbl.Clone() ;

 
    ' configure our global table
    Dim mTable As DataTable
    .
    .
    .
    mTable = tbl.Clone()

Now I can use recursion to loop through the data in my original table and append items to my cloned table. Notice that I use a Select() method to ensure that I pass in the top-level rows to start with. Also pay attention to the ImportRow() and the GetChildRows() method calls (see sidebar below):

    // pass in the top-level rows
    ComputeHierarchy( tbl.Select("ParentId=0"), 0 ) ;
    .
    .
    .
    private void ComputeHierarchy( DataRow[] members, Int32 depth ) 
    {
        foreach( DataRow member in members )
        {
            member["Depth"] = depth ;
            mTable.ImportRow( member ) ;
            ComputeHierarchy( member.GetChildRows("ParentChild"), depth + 1 ) ;
        }
    }

 
    ' pass in the top-level rows
    ComputeHierarchy(tbl.Select("ReportsTo=0"), 0)
    .
    .
    .
    Sub ComputeHierarchy(ByVal members() As DataRow, ByVal depth As Int32)
        Dim member As DataRow
        For Each member In members
            member.Item("Depth") = depth
            mTable.ImportRow(member)
            ComputeHierarchy(member.GetChildRows("ParentChild"), depth + 1)
        Next
    End Sub

Temp DataTable (mTable) after recursion

As you can see, the data is now correctly ordered and ready for display; as mentioned before, I can use the Depth value to determine my indent width when drawing my hierarchical structure.

Step 3 : Painting the data

Finally, now that I have my data arranged and in the correct order all that remains is to create a WebControl and bind to it!

    EmployeeTable.DataSource = mTable.DefaultView ;
    EmployeeTable.DataBind() ;

 
    EmployeeTable.DataSource = mTable.DefaultView
    EmployeeTable.DataBind()

WebControl

    <asp:Repeater id="Repeater1" runat="server">
        <ItemTemplate>
            <img 
                width='<%# 
                Int32.Parse(DataBinder.Eval(Container.DataItem, "Depth")) * 20 
                %>' 
                height="1" />
            <%# DataBinder.Eval(Container.DataItem, "Name") %>
            <br />
        </ItemTemplate>
    </asp:Repeater>

Packaging for reuse

Having done all that hard work, all that remains is to package the code that does the ordering of the hierarchy into its own class so that we can use it over and over again. The following class exposes a Type named OrderedHierarchy that you can use for this very purpose.

To create the OrderedHierarchy Type

1. save the following code into a file named OrderedHierarchy.vb.
2. Create and compile the module by typing the following command at the VS.NET command prompt:
   
   vbc /t:library /r:System.dll,System.Data.dll OrderedHierarchy.vb

You can now save the OrderedHierarchy assembly into the \bin folder of your projects and re-use it.

Option Strict On

Imports System
Imports System.Data


Namespace Samples

    Public Class OrderedHierarchy

        ' Receives a Table and orders the rows based on a specific relationship and
        ' a parent column.
        Public Shared Function GetOrderedTable( _
                        ByVal baseTable As DataTable, _
                        ByVal relationshipName As String, _
                        ByVal parentColumnName As String _
                    ) As DataTable

            ' Configure the ordered table that will be passed out to the client
            Dim tbl As DataTable = baseTable.Clone()
            tbl.Columns.Add(New DataColumn("Depth", GetType(Int32)))
            ComputeHierarchy(tbl, baseTable.Select(parentColumnName & "=0"), 0)
            Return tbl
        End Function

        ' Recursive routine that appends rows to the Private 
        ' table in an ordered manner
        Private Shared Sub ComputeHierarchy( _
                        ByRef orderedTable As DataTable, _
                        ByVal members() As DataRow, _
                        ByVal depth As Int32 _
                    )

            Dim member As DataRow
            For Each member In members
                orderedTable.ImportRow(member)
                orderedTable.Rows(orderedTable.Rows.Count - 1).Item("Depth") = depth
                ComputeHierarchy(orderedTable, member.GetChildRows("ParentChild"), depth + 1)
            Next
        End Sub

    End Class

End Namespace

Click here to view a working sample

There's a couple of excellent articles and ideas that follow on from where this article ends. For an advanced sample that deals with unlimited levels, Teemu Keiski's example is excellent and extends this example by showing how to declaratively wire the data to a TreeView. If you are dealing with just a couple of levels, Thomas Johansen's "Master/Detail" example is second to none!

• Teemu Keiski's example - http://www.aspalliance.com/joteke/treeviewarticle/article.aspx
• Thomas Johansen's example - http://aspalliance.com/aylar/ViewArticle.aspx?ArticleID=4