Nested Sets

Nested Sets provide a fantastic way of traversing hierarchical data. Once processed, they are able to very rapidly walk large data trees.

Suppose you're given a list of products and are asked:

• "What products does the clothing category contain?"

• "What products are my siblings?"

• "Do I have any products under my category?"

All of these questions are easily answered by processing the list of items into a Nested Set. Once the conversion process is finished, it's very easy to query the set and it's incredibly fast.

Example - Products

//Adjacency list
List<Product> productList = new List<Product>
{
    //Root
    new Product() { id = 0, name = "All Products" },

    // L1 nodes
    new Product() { id = 1, parent = 0, name = "Electronics" },
    new Product() { id = 2, parent = 0, name = "Food" },
    new Product() { id = 3, parent = 0, name = "Clothing" },

    //L2 nodes
    new Product() { id = 4, parent = 1, name = "Phones" },
    new Product() { id = 5, parent = 1, name = "Televisions" },
    new Product() { id = 6, parent = 1, name = "Computers" },
    new Product() { id = 7, parent = 2, name = "Frozen" },
    new Product() { id = 8, parent = 2, name = "Fresh" },
    new Product() { id = 9, parent = 3, name = "Shirts" },
    new Product() { id = 10, parent = 3, name = "Pants" },

    //L3 nodes
    new Product() { id = 11, parent = 4, name = "Samsung" },
    new Product() { id = 12, parent = 4, name = "Apple" },
    new Product() { id = 13, parent = 4, name = "Windows" },
    new Product() { id = 14, parent = 7, name = "Pizza" },
    new Product() { id = 15, parent = 7, name = "Vegetables" },


};

Class used in this example

The sample class is here

public class Product
{
    public int id { get; set; } = 0;
    public int parent { get; set; } = 0;
    public string name { get; set; }
}

SDK

Converting the list

To convert a list of items to a nested set, simply create a new NestedSet by supplying the Root, ID, and Parent fields.

var nsProduct = new NestedSet<Product>(productList, 
    
    //Select the first item that has an ID of 0. This is our root.
    (l) => l.First(f => f.id == 0), 
    
    //Select the ID(key) field, and the Parent(fk) field 
    (f) => f.id, (f) => f.parent);

Once finished, this gives you access to all of the other query abilities

Upline

Upline is how you traverse a tree upwards. So starting from key 15(vegetables), let's walk all the way back to "All Products".

foreach (var item in nsProduct.Upline(15, true)) 
    Console.WriteLine($"[{item.HLevel}]({item.ID}) {item.Node.name}");

//Prints:
//[4](15) Vegetables
//[3](7) Frozen
//[2](2) Food
//[1](0) All Products

Downline

Downline is how you traverse a tree downwards. So starting from key 1(electronic), let's walk all the way down.

foreach (var item in nsProduct.Downline(1, true)) 
    Console.WriteLine($"[{item.HLevel}]({item.ID}) {item.Node.name}");

//Prints:
//[2](1) Electronics
//[3](6) Computers
//[3](5) Televisions
//[3](4) Phones
//[4](13) Windows
//[4](12) Apple
//[4](11) Samsung

Siblings

Siblings is how you traverse a tree sideways. So starting from key 14(pizza), let's see what other siblings we have.

foreach (var item in nsProduct.Siblings(14, true)) 
    Console.WriteLine($"[{item.HLevel}]({item.ID}) {item.Node.name}");

//Prints:
//[4](15) Vegetables
//[4](14) Pizza

The Nested Set Node

Every item is converted by creating a new NestedSet<T> class, where the generic parameter is the type of objects that were originally processed. This class provides several additional properties available for use, as well as access to the original class used to convert.

Here's an example of retrieving the root node (key 0).

var NestedNode_Root = nsProduct[0];

Let's look at some of the properties of this NestedSet<Product> below.

ID / ParentID

These properties are assigned from the lookup. They are the ID and Parent fields from the supplied class

HLevel

This property is the horizontal level in the tree, starting from 1(root) to n(lowest level)

Left / Right

These properties are the left and right identifiers for where the node is located in the tree

NodeNumber

A numbered index starting from 1, moving down and across the tree

NodeCount

How many nodes does this node contain in it's downline, including itself.

Node

The original class, in our example, this is a Product.