Algorithm to Clone a Graph in C#

Question

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

What is the mistake in this code - Clone a graph . It says

Object Reference not set to an instance of an object in LeetCode for this line - target.Add(C);.

Could someone share some suggestions here.

public class Node {
    public int val;
    public IList<Node> neighbors;

    public Node(){}
    public Node(int _val,IList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;}

public class Solution {
      public Node CloneGraph(Node node) {
        if (node == null)
        {return null;}
    var map = new Dictionary<int, Node>();
       Queue<Node>  q = new Queue<Node>();
        q.Enqueue(node);
        Node newNode = new Node();
        newNode.val = node.val;
        CopyList(node.neighbors,newNode.neighbors);   

        map.Add(newNode.val, newNode);

        while(q.Count!=0)
        {
            Node head = q.Dequeue();
            Node cloneU = map[head.val];
            foreach (Node neighborNode in head.neighbors)
            {
                if(map.ContainsKey(neighborNode.val))
                {
                    CopyList(head.neighbors,cloneU.neighbors);            
                }
                else
                {
                    q.Enqueue(neighborNode);
                    Node neighborNodeCopy = new Node(neighborNode.val,neighborNode.neighbors);
                    map.Add(neighborNodeCopy.val, neighborNodeCopy);
                    CopyList(neighborNodeCopy.neighbors,cloneU.neighbors);                  
                }
            }
        }            
        return newNode;    
    }

    public void CopyList(IList<Node> source, IList<Node> target)
    {
        foreach( Node C in source)
        {
            target.Add(C);
        }
    }
}

That means that `target` is `null`. Try adding a line before your `foreach` that sets `target` to a new list if it's null: `if (target == null) target = new List();` — Rufus L, Jun 20 '19 at 00:23
You'll need to learn how to [debug](https://learn.microsoft.com/en-us/visualstudio/get-started/csharp/tutorial-debugger?view=vs-2019) your code. — Alex Buyny, Jun 20 '19 at 00:24
You don't initialize `neighbors` in your parameterless constructor (and don't check it for being not `null` in the other) nor in the declaration. — sticky bit, Jun 20 '19 at 00:28
Note that `target.Add(C)` is adding a *reference* to `C` to the `target`, not a clone. So it's not a deep copy. — Rufus L, Jun 20 '19 at 00:37

Rufus L · Answer 1 · 2019-06-20T01:05:19.553

The specific error you're seeing is due to the fact that target is null, and you're trying to call a method (Add) on it.

To fix this, you can just set target to a new list if it's null before you try to call the .Add method on it:

public void CopyList(IList<Node> source, IList<Node> target)
{
    if (target == null) target = new List<Node>();

    foreach( Node C in source)
    {
        target.Add(C);
    }
}

However, this is identical to a one-line version of the code, using the System.Linq extension method, ToList"

public void CopyList(IList<Node> source, IList<Node> target)
{
    target = source?.ToList();
}

With that being said, it appears that you're trying to make a deep copy of Node, but when you do target.Add(C);, you're adding a reference to the source node instead of a clone of that node.

For deep copying, we need to make a complete copy of all reference types, and in the case of Node, the only reference type it has is the IList<Node> collection. A possibly more simple way to create a deep copy is to implement a Clone method on Node itself, which creates a new Node and then creates a new List<Node> that contains clones of each node in the list:

public class Node
{
    public int Value { get; set; }
    public IList<Node> Neighbors { get; set; }

    public Node() { }

    public Node(int val, IList<Node> neighbors)
    {
        Value = val;
        Neighbors = neighbors;
    }

    public Node Clone()
    {
        // Start with a new node with the same value
        var newNode = new Node { Value = Value };

        // Deep copy the list of neighbors by returning their clones in a new list
        newNode.Neighbors = Neighbors?.Select(node => node.Clone()).ToList();

        // Return our deep copy
        return newNode;
    }
}

Algorithm to Clone a Graph in C#

1 Answers1