-1

I am trying to clone a graph using DFS in Java iteratively, but on compiling it keeps on showing NullPointerException. I know the code using recursion is uch simpler, but wanted to try out in iterative way. The code is shown below:

 /**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node==null) return null;
    Map<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<>();
    Stack<UndirectedGraphNode> st = new Stack<>();
    st.push(node);

    while(!st.isEmpty())
    {
        UndirectedGraphNode n = st.pop(); 
        UndirectedGraphNode copy = null;
        if(!hm.containsKey(n)) //if n is cloned before, no need to clone it again
        {
            copy = new UndirectedGraphNode(n.label); //clone parent
            hm.put(n, copy);
        }
        else
            copy = hm.get(n); 

        for(UndirectedGraphNode neighbor: n.neighbors)
        {
            if(!hm.containsKey(neighbor))
            {
                UndirectedGraphNode copy_neighbor = new UndirectedGraphNode(neighbor.label);
                copy.neighbors.add(copy_neighbor); //clone child.
                hm.put(neighbor, copy_neighbor);
                st.push(neighbor);
            }else
                copy.neighbors.add(hm.get(neighbor));//this handles parent node as well.
        }

    }
    return hm.get(node);   
}

Here, what I am tryig to do is get a node from the graph and traverse to it's next connected node or as in this case neighbor.

The NullPointerException is being shown in this line :

copy.neighbors.add(copy_neighbor);

StackTrace

java.lang.NullPointerException
at line 55, Solution.cloneGraph
at line 102, __Driver__.main
Pritom Mazumdar
  • 325
  • 5
  • 20
  • You may want to ensure that `copy` and `copy.neighbors` are not null. – Prashant Zombade Jan 23 '19 at 04:11
  • Please post the exception stacktrace and mark the line that throws it. – c0der Jan 23 '19 at 04:38
  • @c0der, added the `exception stacktrace` and also I have pointed where the `nullpointer exception` occurs – Pritom Mazumdar Jan 23 '19 at 18:42
  • So use a [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to find which variable is null, or simply add printouts before that line to check `System.out.println(copy==null);` and `System.out.println(copy.neighbors==null);` – c0der Jan 24 '19 at 04:45

1 Answers1

0

You probably are not initialing the neighbors attribute on the UndirectedGraphNode class. Make sure you initialize, either on the attribute declaration:

private List<UndirectedGraphNode> neighbors = new ArrayList<>();

Or in the constructor:

public UndirectedGraphNode(String label) {
   ...
   neighbors = new ArrayList<>();
}
Daniel Pereira
  • 2,720
  • 2
  • 28
  • 40