This question should be rather easy for any Java developer. I swear I looked it up after spending ~2 hours on it, but I can't really understand what's wrong with this code.
Basically, I am implementing Karger's minimum cuts algorithm. It requires me to keep merging nodes in a graph and then compute the number of crossing edges at the end (an int value). This algorithm must be repeated n times, always from the starting graph. My problem is that I am unable to create a deep copy of my Graph object, and I can't find the mistake.
I have cropped the code to just show the problem and no more, but I am still unable to figure out what's wrong. Here the code is.
Class Node:
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 Graph:
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, i.e. 7
Graph.printAdjList(G.AdjList.get(0));
Graph.printAdjList(R.AdjList.get(0));
}
}
Output:
5 : 19, 1,
5 : 19, 1,
This kind of puzzles me to be honest. I understand that Java is pass by value only, 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 am moving through every adjacency list and then I am making a deep copy of the Node. I don't understand why invoking .setNode() on the copied object modifies also the original object (that has a different reference).
Previous answers like 1 seem to go the same direction I am going, what am I missing here? :S
