C# algorithm for generating hierarchy

Question

I've got a text file that looks like this:

{ Id = 1, ParentId = 0, Position = 0, Title = "root" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }

I'm looking for a generic C# algorithm that will create an object hierarchy from this. A "Hierarchize" function, if you will, that turns this data into an object hierarchy.

Any ideas?

edit I've already parsed the file into .NET objects:

class Node
{
    public int Id { get; }
    public int ParentId { get; }
    public int Position { get; }
    public string Title { get; }
}

Now I need to actually arrange the objects into an object graph.

Answer 1

Many thanks to Jon and to mquander - you guys gave me enough information to help me solve this in a proper, generic way. Here's my solution, a single generic extension method that converts objects into hierarchy form:

public static IEnumerable<Node<T>> Hierarchize<T, TKey, TOrderKey>(     this IEnumerable<T> elements,      TKey topMostKey,      Func<T, TKey> keySelector,      Func<T, TKey> parentKeySelector,      Func<T, TOrderKey> orderingKeySelector) {     var families = elements.ToLookup(parentKeySelector);     var childrenFetcher = default(Func<TKey, IEnumerable<Node<T>>>);     childrenFetcher = parentId => families[parentId]         .OrderBy(orderingKeySelector)         .Select(x => new Node<T>(x, childrenFetcher(keySelector(x))));      return childrenFetcher(topMostKey); } 

Utilizes this small node class:

public class Node<T> {     public T Value { get; private set; }     public IList<Node<T>> Children { get; private set; }      public Node(T value, IEnumerable<Node<T>> children)     {         this.Value = value;         this.Children = new List<Node<T>>(children);     } } 

It's generic enough to work for a variety of problems, including my text file issue. Nifty!

****UPDATE****: Here's how you'd use it:

// Given some example data: var items = new[]  {    new Foo()     {       Id = 1,       ParentId = -1, // Indicates no parent       Position = 0    },    new Foo()     {       Id = 2,       ParentId = 1,       Position = 0    },    new Foo()     {       Id = 3,       ParentId = 1,       Position = 1    } };  // Turn it into a hierarchy!  // We'll get back a list of Node<T> containing the root nodes. // Each node will have a list of child nodes. var hierarchy = items.Hierarchize(     -1, // The "root level" key. We're using -1 to indicate root level.     f => f.Id, // The ID property on your object     f => f.ParentId, // The property on your object that points to its parent     f => f.Position, // The property on your object that specifies the order within its parent     ); 

Answer 2

Hmm... I don't quite see how that works. How can 2 and 5 both have parent=1, position=0? Should 5 have parent 2, 3 or 4?

Okay, this new version goes through the all the nodes three times:

• Load all nodes and put them into the a map
• Associate each node with its parent
• Sort each node's child by position

It's not well-encapsulated, nicely error checking etc - but it works.

using System;
using System.Collections.Generic;
using System.IO;

public class Node
{
    private static readonly char[] Braces = "{}".ToCharArray();
    private static readonly char[] StringTrim = "\" ".ToCharArray();

    public Node Parent { get; set; }
    public int ParentId { get; private set; }
    public int Id { get; private set; }
    public string Title { get; private set; }
    public int Position { get; private set; }
    private readonly List<Node> children = new List<Node>();
    public List<Node> Children { get { return children; } }

    public static Node FromLine(string line)
    {
        Node node = new Node();
        line = line.Trim(Braces);
        string[] bits = line.Split(',');
        foreach (string bit in bits)
        {
            string[] keyValue = bit.Split('=');
            string key = keyValue[0].Trim();
            string value = keyValue[1].Trim();
            switch (key)
            {
                case "Id":
                    node.Id = int.Parse(value);
                    break;
                case "ParentId":
                    node.ParentId = int.Parse(value);
                    break;
                case "Position":
                    node.Position = int.Parse(value);
                    break;
                case "Title":
                    node.Title = value.Trim(StringTrim);
                    break;
                default:
                    throw new ArgumentException("Bad line: " + line);
            }
        }
        return node;
    }

    public void Dump()
    {
        int depth = 0;
        Node node = this;
        while (node.Parent != null)
        {
            depth++;
            node = node.Parent;
        }
        Console.WriteLine(new string(' ', depth * 2) + Title);
        foreach (Node child in Children)
        {
            child.Dump();
        }
    }
}

class Test
{       
    static void Main(string[] args)
    {
        var dictionary = new Dictionary<int, Node>();

        using (TextReader reader = File.OpenText("test.txt"))
        {
            string line;
            while ((line = reader.ReadLine()) != null)
            {
                Node node = Node.FromLine(line);
                dictionary[node.Id] = node;
            }
        }
        foreach (Node node in dictionary.Values)
        {
            if (node.ParentId != 0)
            {
                node.Parent = dictionary[node.ParentId];
                node.Parent.Children.Add(node);
            }
        }

        foreach (Node node in dictionary.Values)
        {
            node.Children.Sort((n1, n2) =>
                               n1.Position.CompareTo(n2.Position));
        }

        Node root = dictionary[1];
        root.Dump();
    }
}

Sample text file:

{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 1, ParentId = 0, Position = 0, Title = "root" }

Output:

root
  child 1
  child 2
  child 3
    grandchild 1

Answer 3

Once you have the file parsed in you can follow this blog on how to assemble the objects into a hierarchy using LINQ.