Simple Java objects not deep copying

Question

This question should be fairly simple for any Java developer. I swear I looked at it, spending ~ 2 hours on it, but I can’t understand what is wrong with this code.

Basically, I implement the Karger minimum cut algorithm. This requires me to continue merging the nodes in the graph and then calculate the number of intersecting edges at the end (int value). This algorithm should be repeated n times, always from the initial schedule. My problem is that I cannot create a deep copy of my Graph object, and I cannot find the error.

I cut the code to just show the problem, and nothing more, but I still can’t understand what happened. Here is the code.

Node Class:

public class Node { public Integer Data; public Node() { Data = 0; } public Node(Node rhs) { Data = rhs.Data.intValue(); } public Node(Integer rhs) { Data = rhs.intValue(); } public void setNode(Integer rhs) { Data = rhs; } 

Class Schedule:

 public class Graph { public ArrayList<ArrayList<Node>> AdjList; public ArrayList<Node> NodeSet; // This contains all the nodes public Graph() { AdjList = new ArrayList<ArrayList<Node>>(); NodeSet = new ArrayList<Node>(); } public Graph(Graph G) { AdjList = new ArrayList<ArrayList<Node>>(); for (ArrayList<Node> L : G.AdjList) { ArrayList<Node> Lcopy = new ArrayList<Node>(); for (Node N : L) { Node copy = new Node(N); Lcopy.add(copy); } AdjList.add(L); } } public void addNewAdjList(ArrayList<Node> NodeAdjList) { // Input is the adjacency list of a new node // The first element in the NodeAdjList is the node itself, the rest is the adj nodes AdjList.add(NodeAdjList); } public static void printAdjList(ArrayList<Node> Adjlist) { Node start = Adjlist.get(0); System.out.print(start.Data + " : "); for (int j=1; j < Adjlist.size(); ++j) { System.out.print(Adjlist.get(j).Data + ", "); } System.out.print("\n"); } 

Main:

 public class Main { /** * @param args */ public static void main(String[] args) { Node Five = new Node(5); Node Seven = new Node(7); Node One = new Node(1); Graph G = new Graph(); ArrayList<Node> L = new ArrayList<Node>(); L.add(Five); L.add(Seven); L.add(One); G.addNewAdjList(L); Graph R = new Graph(G); R.AdjList.get(0).get(1).setNode(19); // Gets node #1 in the first adj list, ie 7 Graph.printAdjList(G.AdjList.get(0)); Graph.printAdjList(R.AdjList.get(0)); } 

}

Output:

5: 19, 1,

5: 19, 1,

This type puzzles me, to be honest. I understand that Java is passed only by value, but objects are always represented by their reference. As far as I understand, my copy constructor for G should always make a deep copy: I go through each adjacency list and then make a deep copy of Node. I do not understand why calling .setNode () for the copied object also changes the original object (which has a different reference).

Previous answers like 1 seem to go in the same direction as me, what am I missing here ?: S

Answer 1

Your mistake:

 ArrayList<Node> Lcopy = new ArrayList<Node>(); for (Node N : L) { Node copy = new Node(N); Lcopy.add(copy); } AdjList.add(L); 

You created a copy of L (called Lcopy ), but then you added the original L to the cloned graph. To fix this, the last line should be as follows:

 AdjList.add(Lcopy); 

Note. If you used a reasonable name for your variable instead of L , this error probably would never have happened!