C# How to make graph objects cloneable

Question

I've got newbie question, problem which I have to solve, to keep moving forward with my Unity project... It's probably pretty easy, but I'm not a programmer and a just don't know how to implement something I need. I checked documentation, but still don't know how to do it :/

I'm using graph class and I need to clone graph objects. Already know it's necessary to write deep clone function, coz I need NO references, just list of independent objects.

What I need is: create list of graphs. Change first one (by adding some edges), and clone it to the 2nd position on the list. Change 2nd (without changing 1st), and clone it to the 3rd position on the list, and so on...

This is my starting point:

public class Graph<T>
    {
        public int xMatrix;
        public int yMatrix;
        public int[] vertices;
        public Graph() { }

        public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges)
        {
            foreach (var vertex in vertices)
                AddVertex(vertex);

            foreach (var edge in edges)
                AddEdge(edge);
        }

        public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();

        public void AddVertex(T vertex)
        {
            AdjacencyList[vertex] = new HashSet<T>();
        }

        public void AddEdge(Tuple<T, T> edge)
        {
            if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2))
            {
                AdjacencyList[edge.Item1].Add(edge.Item2);
                AdjacencyList[edge.Item2].Add(edge.Item1);
            }
        }
    } 

And what I tried:

public class Graph<T> :ICloneable
{
    public int xMatrix;
    public int yMatrix;
    public int[] vertices;
    public IEnumerable<int> verts;
    public IEnumerable<Tuple<int, int>> edgs;

    public Graph() { }

    public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges)
    {
        foreach (var vertex in vertices)
            AddVertex(vertex);

        foreach (var edge in edges)
            AddEdge(edge);
        verts = (IEnumerable<int>)vertices;
        edgs = (IEnumerable<Tuple<int, int>>)edges;
    }

    public Dictionary<T, HashSet<T>> AdjacencyList { get; set; } = new Dictionary<T, HashSet<T>>();

    public void AddVertex(T vertex)
    {
        AdjacencyList[vertex] = new HashSet<T>();
    }

    public void AddEdge(Tuple<T, T> edge)
    {
        if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2))
        {
            AdjacencyList[edge.Item1].Add(edge.Item2);
            AdjacencyList[edge.Item2].Add(edge.Item1);
        }

                        //this.edgs.Append<edge>;
                        //IEnumerable<Tuple<int, int>> newEdgs = this.edgs.Append<Tuple<edge.Item1, edge.Item2>;
                        //IEnumerable<Tuple<int, int>> newEdgs = this.edgs.Append<edge>;
        //???
    }

    public object Clone()
    {
        IEnumerable<int> vertices = this.verts;
        IEnumerable<Tuple<int, int>> edges = this.edgs;
        Graph<int> other = new Graph<int>(vertices, edges);
        return other;
    }
}

Thank you in advance!

Answer 1

For the most part your implementation doesn't have any inherent flaws.

The issue that might arise from the IEnumerables that you are passing around.

When you store an enumerable object, such as an array of integers inside of a IEnumerable variable you aren't copying the values but rather just storing the address(reference) to the original object, unless that object itself is a value type.

If the original type is a reference type, whether mutable or not, such as an array, we can work around this by copying the content of the reference type, for arrays we could use .CopyTo(destinationArray).

Another thing that might mess with you is that Tuple<> unlike ValueTuple or (type,type) is an immutable reference type.

Most of this can be avoided though. If you feel comfortable modifying how you clone the object, you can instead copy AdjacencyList instead.

public class Graph<T>
{
    public int xMatrix;
    public int yMatrix;
    public int[] vertices;

    public Dictionary<T, HashSet<T>> AdjacencyList => _AdjacencyList;

    protected Dictionary<T, HashSet<T>> _AdjacencyList = new Dictionary<T, HashSet<T>>();

    public Graph() { }

    public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges) { }

    public void AddVertex(T vertex) { }

    public void AddEdge(Tuple<T, T> edge) { }

    public object Clone()
    {
        Graph<T> newGraph = new Graph<T>()
        {
            yMatrix = this.yMatrix,
            xMatrix = this.xMatrix,
            vertices = new int[vertices.Length]
        };

        vertices.CopyTo(newGraph.vertices, 0);

        newGraph._AdjacencyList = new Dictionary<T, HashSet<T>>(AdjacencyList.Select(x =>
        {
            T[] copied = new T[x.Value.Count];

            x.Value.CopyTo(copied);

            return new KeyValuePair<T, HashSet<T>>(x.Key, new HashSet<T>(copied));
        }));

        return newGraph;
    }
}

Answer 2

So... with some help 'of the Internet' problem is finally solved:

Code from DekuDesu’s answer works great in VS C# console applications with .NET Core 3.1 or .NET 5.0, but Unity engine doesn't support that.

Fix for that is change code to work in VS in C# ClassLibrary (.NET Framework 4.7.1 & Unity settings on .NET 4.x) or (.NET Standard & Unity settings on .NET Standard 2.0).

The ability to construct a new Dictionary<> with an IEnumerable<KeyValuePair> isn't available in .NET Framework. Alternatively I used IEnumerable<>.ToDictionary() and it worked.

This works:

public class Graph<T>
{
    public int xMatrix;
    public int yMatrix;
    public int[] vertices;

    public Dictionary<T, HashSet<T>> AdjacencyList => _AdjacencyList;

    protected Dictionary<T, HashSet<T>> _AdjacencyList = new Dictionary<T, HashSet<T>>();

    public Graph() { }

    public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges)
    {
        foreach (var vertex in vertices)
            AddVertex(vertex);

        foreach (var edge in edges)
            AddEdge(edge);
    }

    public void AddVertex(T vertex)
    {
        AdjacencyList[vertex] = new HashSet<T>();
    }

    public void AddEdge(Tuple<T, T> edge)
    {
        if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2))
        {
            AdjacencyList[edge.Item1].Add(edge.Item2);
            AdjacencyList[edge.Item2].Add(edge.Item1);
        }
    }

    public object Clone()
    {
        Graph<T> newGraph = new Graph<T>()
        {
            yMatrix = this.yMatrix,
            xMatrix = this.xMatrix,
            vertices = new int[vertices.Length]
        };

        vertices.CopyTo(newGraph.vertices, 0);

        newGraph._AdjacencyList = AdjacencyList.Select(x =>
        {
            T[] copied = new T[x.Value.Count];

            x.Value.CopyTo(copied);

            return new KeyValuePair<T, HashSet<T>>(x.Key, new HashSet<T>(copied));
        }).ToDictionary(o => o.Key, o => o.Value);

        return newGraph;
    }
}

Thanks for your help!