How to clone an object graph and keep relationships of objects intact?

Question

In my ASP.net core application with Angular 2+ client, I work with a complicated object graph. In the object graph I have some objects with references to each other. I have a simplification included as an illustration below, where MainObject represents the graph:

public class MainObject
{
    public int Id { get; set; }   
    public ObjectProperty MyProperty { get; set; }
    public List<GreenObject> GreenObjects { get; set; }
    public List<YellowObject> YellowObjects { get; set; }
}

public class GreenObject
{
    public int Id { get; set; }
    public Guid Guid { get; set; }
    public GreenObjectProperties MyProperty { get; set; }
    public Guid? YellowObjectRef { get; set; }
}
public class YellowObject
{
    public int Id { get; set; }
    public Guid Guid { get; set; }
    public YellowProperties MyProperty { get; set; }
    public Guid? GreenObjectRef { get; set; }
}

Now I have the requirement to create clones of MainObject, such that any relationship between objects in the object graph is maintained, but also such that it can be persisted. This means I need new UUID/GUID for the clone (to be able to be persisted in my DB), and continue to respect the relationship to the cloned objects and thus the newly created UUID/GUID's.

I am already using Automapper in my ASP.net application, so I was considering to use this library to create the clone. But I am willing to consider other libraries, or even to perform the cloning on the client side.

Question: Is there a common pattern or library to easily clone the object graph, creating new UUID/GUID's while keeping the references to the newly created objects/GUID's?

In the simplification I could easily iterate over the list of GreenObject issue new GUID and then find the YellowObject where GreenObjectRef equals the original GUID and replace it with the new GUID (and vice versa for the list of YellowObject). However my actual implementation is very complicated, and writing such a custom cloning method that is specific to the relationship would also be troublesome to maintain.

Answer 1

The problem of copying the object graph and the problem of assigning new GUIDs to the object graph are very similar, but they can be handled separately and one after another, so let me start with copying first.

In case the object graph is just a tree, there may be a simpler solution, but in a comment you mentioned several MainObjects sharing references to Green and Yellow objects, so let me assume the graph is not a tree. The following solution could be simplified for the specific example in the question, but I guess your real graph is more complicated, so I will give you a general answer which works for arbitrary object graphs.

I would solve this in 3 stages:

1. Determine all objects within the object graph. This can be accomplished by a standard graph traversal (like a simple depth-first search), with a Hashmap<object> where the already visited objects are held. The collection will serve for not visiting any object twice, and at the end it will held all the objects in the graph. All your objects which hold references to other objects will require something like a AddReferences(Hashmap<object> alreadyVisited) method for this.

2. Make shallow copies of the found objects. For this, it is best to let each object implement the ICloneable interface, utilizing MemberwiseClone. Put the result into a Dictionary which maps each "old" object to its clone.

3. Make a second graph traversal where the dictionary is passed to all "new" objects which can then replace all references to "old" objects they have to the new clones. Your objects will require a method like a ReplaceReferences(Dictionary<object,object> objectMap) for this.

Note I assumed the references to the objects can be used as keys here (in case you have overriden the Equals and GetHashCode methods, have a look into this SO post).

The GUID generation/replacement can be implemented in a similar fashion:

1. Graph traversal for determination of all GUIDs

2. Generation of new GUIDs and filling a dictionary which maps each "old" GUID to the related new one

3. Graph traversal for replacing the GUIDs

And no, I don't any library which can solve or support this. Note no library knows by itself which of the references inside a custom object graph belong themselves to the graph, and which ones are just references to objects "outside" the graph, that is knowledge one has always to encode somewhere, no lib can do this completely automatically.

Answer 2

1. Memberwise clone all the green and yellow objects
2. Walk the list of green and yellow objects and update their Guids
3. Add the old and new guid pairs to a Dictionary
4. Walk the list of green and yellow objects again and swap the Refs using the Dictionary created in the previous step

You can also serialize and then deserialize to a format that supports object references, like protobuf or maybe avro. You'd have to have actual object references however (not GUIDs).

Answer 3

Following Doc Brown's recommended steps of GUID generation/replacement, and this SO answer to recursively go through all properties of the object graph (https://stackoverflow.com/a/20554262/10340388) I came with the following solution. The function is recursive for collections of objects as well as classes that could hold GUID's. It can probably be cleaned up and made DRY-er, but it works for me so far.

Creation of the dictionary:

private Dictionary<Guid, Guid> CreateDictionaryOfGuids(object obj, Dictionary<Guid, Guid> guidDictionary)
{
    Type objType = obj.GetType();  // Type of object
    PropertyInfo[] typeProperties = objType.GetProperties();  // Properties of type
    foreach (PropertyInfo property in typeProperties) // Go through all properties
    {
        object propValue = property.GetValue(obj, null); // Get the value of that property in Obj
        Type propType = property.PropertyType;
        var elems = propValue as IList;  // cast the value of the property as IList 
        if (elems != null) // and see if it's valid if != null
        {
            foreach (var item in elems)  // If IList become recursive into the collection
            {
                Type itemType = item.GetType();
                if (PropertyTypeRequiresRecursive(itemType))
                    guidDictionary = CreateDictionaryOfGuids(item, guidDictionary); 
            }
        } 
        else if (propType == typeof(Guid)) // Check if property is a Guid
        {
            Guid existingGuid = (Guid)property.GetValue(obj, null);
            if (!guidDictionary.ContainsKey(existingGuid)) // If Guid doesn't exist in dictionary
            {
                Guid newGuid = Guid.NewGuid();
                guidDictionary.Add(existingGuid, newGuid);  // Add the old and the new Guid to the dictionary
            }
        } 
        else if (PropertyTypeRequiresRecursive(propType) && propValue != null)  // Make method recursive into properties of that class
        {
            guidDictionary = CreateDictionaryOfGuids(propValue, guidDictionary); 
        }
    }
    return guidDictionary;
}

Replacement of the GUID values:

private object ReplaceGuids(object obj, Dictionary<Guid, Guid> guidDictionary)
{
    Type objType = obj.GetType();  // Type of object
    PropertyInfo[] typeProperties = objType.GetProperties();  // Properties of type
    foreach (PropertyInfo property in typeProperties) // Go through all properties
    {
        object propValue = property.GetValue(obj, null); // Get the value of that property in Obj
        Type propType = property.PropertyType;
        var elems = propValue as IList;  // cast the value of the property as IList 
        if (elems != null) // and see if it's valid if != null
        {
            for (int i = 0; i < elems.Count; i++) // If IList become recursive into the collection
            {
                Type itemType = elems[i].GetType();
                if (PropertyTypeRequiresRecursive(itemType))
                    elems[i] = ReplaceGuids(elems[i], guidDictionary); 
            }
        } else if (propType == typeof(Guid)) // Check if property is a Guid
        {
            Guid existingGuid = (Guid)property.GetValue(obj, null);
            if (guidDictionary.ContainsKey(existingGuid))
            {
                Guid newGuid = guidDictionary[existingGuid];
                property.SetValue(obj, newGuid);  // set to the new GUID from dictionary
            }
        } else if (PropertyTypeRequiresRecursive(propType) && propValue != null)  // Make method recursive into properties of that class
        {
            object newPropValue = ReplaceGuids(propValue, guidDictionary);
            property.SetValue(obj, newPropValue);
        }
    }
    return obj;
}

private bool PropertyTypeRequiresRecursive(Type type)
{
    bool propIsPrimitive = type.IsPrimitive;
    if (propIsPrimitive == true || type == typeof(string) || type == typeof(DateTime)) return false;
    return true;
}

and then I call this in the following fashion, where MainObject mainObject is assumed to already be a deep copy/clone:

Dictionary<Guid, Guid> guidDictionary = new Dictionary<Guid, Guid>();
guidDictionary = CreateDictionaryOfGuids(mainObject, guidDictionary);
mainObject = (MainObject)ReplaceGuids(mainObject, guidDictionary);