C# - Recursive Grouping

Question

I have a List of objects of type IGroup. These can be nested to an umlimited level, and I'm trying to group them after retrieving them from a database. I can't get my head around how to recursively add all groups to the right parents. Any groups with null as a parent are top level groups. I can't guarantee the order they come out of the database.

public interface IGroup {
  string ID { get; set; }
  string Name { get; set; }
  string ParentID { get; set; }
  IList<IGroup> Groups { get; set; }
  ...

So if I had a list of:

Group1: ID = g1, ParentID = null
Group1a: ID = g2, ParentID = g1
Group2: ID = g3, ParentID = null
Group1b: ID = g4, ParentID = g3
Group1bc: ID = g5, ParentID = g4

I'm trying to group them as:

|Group1
|--Group1a
|--Group1b
|--|
   |--Group1bc
|Group2

Anyone fancy a stab at grouping them recursively?

Answer 1

You could try ordering them by parent id, assuming that the parent group is always created before the child group.

Answer 2

Group by ParentID (Linq: GroupBy), order by ID.

Start with an empty root node (ID: null) and add all items with this ParentID. Recursively continue this process for any item that has been added.

Answer 3

No need to be recursive. To wit:

var lookup = items.ToDictionary(g => g.ID); // items is IEnumerable<IGroup>
foreach (var item in items.Where(g => g.ParentID != null)) {
    lookup[item.ParentID].Groups.Add(item);
}
var parents = items.Where(g => g.ParentID == null);

Note that lookup[item.ParentID] will throw if there is no IGroup with the corresponding ParentID. You can handle this more gracefully with TryGetValue.

My implementation of IGroup:

public class Group : IGroup {
    public string ID { get; set; }
    public string Name { get; set; }
    public string ParentID { get; set; }
    public IList<IGroup> Groups { get; set; }
    public Group() {
        Groups = new List<IGroup>();
    }
}

My test items:

IEnumerable<IGroup> items = new List<IGroup>() {
    new Group() { ID = "g1", ParentID = null },
    new Group() { ID = "g2", ParentID = "g1" },
    new Group() { ID = "g3", ParentID = null },
    new Group() { ID = "g4", ParentID = "g3" },
    new Group() { ID = "g5", ParentID = "g4" },
    new Group() { ID = "g6", ParentID = "g5" }
};

Answer 4

As you extract each element from the database, you need to add it to its parent. So keep a Dictionary to help find the parent. If you get a child before its parent, then you can insert a placeholder until you get the real thing.

void BuildGroups()
{
   foreach( IGroup x /* obtained from database or a collection or wherever */ )
      AddGroup( x );
}

Dictionary<string,IGroup> _groups = new Dictionary<string,IGroup>;
string _parentGroupName = "PARENT";
void AddGroup( IGroup x )
{
    // locate (or create) parent and add incoming group
    IGroup parent;
    string parentID = x.ParentID ?? _parentGroupName;
    if( !groups.TryGetValue( parentID, out parent ) )
    {
       parent = new Group( parentID ); // SEE NOTE BELOW!
       _groups[parentID] = parent;
    }
    parent.Groups.Add( x );

    // locate (or insert) child, and make sure it's up to date
    IGroup child;
    if( groups.TryGetValue( x.ID, out child ) )
    {
       // We must have inserted this ID before, because we found one
       // of ITS children first.  If there are any other values besides
       // ParentID and ID, then copy them from X to child here.
    }
    else
    {
       // first time we've seen this child ID -- insert it
        _groups[x.ID] = x;
    }

}

The dictionary element at _parentGroupName will then be a dummy node whose children are all of your top-level groups (i.e. the ones with NULL as ParentID from the database); from that element you can do a recursive traversal:

VisitGroups( _groups[_parentGroupName], "" );

void VisitGroups( string ID, string indent )
{
   IGroup x;
   if( _groups.TryGetValue( ID, out x ) )
   {
       foreach( IGroup y in x.Groups )
       {
          WriteLine( indent + " {0}", y.ID );
          VisitGroups( y.ID, indent + "   " );
       }        
   }
}

NOTE: This implementation runs in a single inline pass through the data -- you can add elements immediately as they're retrieved from the database, and you only need to make a single pass through the data. That means you save some time and some memory. But in return, it requires that you be able to allocate an object with type IGroup() to act as a placeholder, in case a child is retrieved before its parent. You can only avoid that requirement if you know something about the order of the objects or if you process your dictionary in two passes, as is shown in the other answers.

I use a sentinel value, _parentGroupName, to keep the top-level nodes in the same collection as all the others. You can easily alter this to use a separate collection for the top level nodes instead if you prefer.

Answer 5

This is not recursive, but here's a solution (assuming you have all you groups in a list called groups)

var rootGroups = new List<IGroup>();
var dic = groups.ToDictionary(g => g.ID);
foreach (var g in groups)
{
    if (g.ParentID == null)
    {
        rootGroups.Add(g);
    }
    else
    {
        IGroup parent;
        if (dic.TryGetValue(g.ParentID, out parent))
        {
                parent.Groups.Add(g);
        }
    }
}

Answer 6

You could try this

public interface IGroup
{
    string ID { get; set; }  
    string Name { get; set; }  
    string ParentID { get; set; }  
    List<IGroup> Groups { get; set; }
}
public class Group : IGroup
{
    public string ID { get; set; }
    public string Name { get; set; }
    public string ParentID { get; set; }
    public List<IGroup> Groups { get; set; }
    public Group()
    {

    }
    public Group(string id, string name, List<IGroup> childs)
    {
        ID = id;
        Name = name;
        Groups = (List<IGroup>)childs.Cast<IGroup>();
    }

}


class Program
{
    static void Main(string[] args)
    {
        List<IGroup> OriginalList;
        List<IGroup> HirarchList = new List<IGroup>();

        OriginalList = new List<IGroup>() 
        { 
            new Group() { ID = "g1", ParentID = null }, 
            new Group() { ID = "g2", ParentID = "g1" }, 
            new Group() { ID = "g3", ParentID = null }, 
            new Group() { ID = "g4", ParentID = "g3" }, 
            new Group() { ID = "g5", ParentID = "g4" }, 
            new Group() { ID = "g6", ParentID = "g5" } };

        HirarchList = GetCreateList(null,  OriginalList);
    }
    public static List<IGroup> GetCreateList(string id, List<IGroup> list)
    {
        List<IGroup> temp = new List<IGroup>();
        temp = (from item in list 
               where item.ParentID == id
               select (IGroup)new Group(item.ID, item.Name,GetCreateList(item.ID, list))).ToList();

        return (List<IGroup>)temp;
    }

}