How to add children to an object graph in C#, given the parent?

Question

I have several objects in C# that's roughly like this:

A: {
      Id: 1,
      Parent: {
                 Id: 2,
                 Parent: {
                            Id: 3,
                            Parent: null
                         }}}

And,

B: {
     Id: 4
     Parent: {
               Id: 2
               Parent:
                       { 
                         Id: 3
                         Parent: null
}}}

I would like to combine the two and convert so they are inverted:

Combined: {
             Id 3:
             Child: {
                         Id 2,
                         Child: { 
                                     Id: 4,
                                     Child: null
                         Child: {    Id: 1,
                                     Child: null
}}}

The classes look like this:

Public Class MyObject {
    public string Id;
    public MyObject Parent;
}

public Class CombinedObject {
    public string Id;
    public IList<CombinedObject> Child;
}

This should be very easy and there should be a nice declarative way to do this, right? I can't figure it out without using a lot of ugly loops.

Answer 1

There might be better solutions, but here's a stab at it:

MyObject A = GetA(); 
MyObject B = GetB(); 

List<MyObject> allObjects = 
  GetObjects(A) 
  .Concat(GetObjects(B)) 
  .GroupBy(x => x.Id) //rule out duplicates 
  .Select(g => g.First()) 
  .ToList(); 

ILookup<string, string> lookupByParentId = allObjects 
  .Where(x => x.Parent != null) 
  .ToLookup(x => x.Parent.Id, x => x.Id); 

Dictionary<string, CombinedObject> allCombinedObjects = allObjects 
  .Select(x => new CombinedObject() 
  { 
    Id = x.Id, 
    Children = null;
  }) 
  .ToDictionary(x => x.Id); 

foreach(CombinedObject co in allCombinedObjects.Values)
{
  co.Children = lookupByParentId[co.Id]
    .Select(childId => allCombinedObjects[childId])
    .ToList();
}


HashSet<string> rootNodeKeys = new HashSet(allObjects 
  .Where(x => x.Parent == null) 
  .Select(x => x.Id) 
  ); 

List<CombinedObject> rootNodes = allCombinedObjects.Values
  .Where(x => rootNodeKeys.Contains(x.Id)) 
  .ToList(); 

Where GetObjects is defined:

public IEnumerable<MyObject> GetObjects(MyObject source)
{
  MyObject current = source;
  while (current != null)
  {
    yield return current;
    current = current.Parent;
  }  
}