Java Recursion, calling it with Objects - How To Copy The Objects?

Question

The old value/reference things. Im getting ConcurrentModificationException for this adaptation of the Bron-Kerbosch.

public int[] bk(ArrayList<Integer> R, ArrayList<Integer> P, ArrayList<Integer> X) {
    int count[] = new int[n];
    int u=0, c = 0;

    ArrayList<Integer> tempPX = new ArrayList<Integer>();
    ArrayList<Integer> newP = P;
    ArrayList<Integer> newX = X;
    ArrayList<Integer> newR = R;

    if (P.isEmpty() && X.isEmpty()) {
        count[R.size()]++;
    } else {

        u = 0; c = 0; // find vertex with largest degree            
        tempPX.addAll(P); tempPX.addAll(X); // P ⋃ X
        for (Integer v : tempPX) {            
            if (neighbours[v].size() > neighbours[u].size()) {
                u = c; 
            }
            c++;
        } 

        P.removeAll(neighbours[u]); // P \ neighbours[u]
        for (Integer v : newP) {

            newR.add(v); // R ⋃ v

            newP.retainAll(neighbours[v]); // P â‹‚ neighbours[v]

            newX.retainAll(neighbours[v]); // X â‹‚ neighbours[v]

            bk(newR, newP, newX); 

            P.remove(v); // removing object
            X.add(v); // X ⋃ v
        }

    }

    return count;
}

The exception occurs at line for (Integer v : newP), and the recursive call in there. I need to P.removeAll(neighbours[u]); then loop over that resulting list, inside doing the things in the comments, AND PASS COPIES in the recursive call so it wont complain and work not pass the references and keep modifying the same object P/X/R. So how and WHEN do i copy them?? Those first lines.. I'm making copies of the references aren't i... (yes i know i "modify" newP then loop over the old P, they just point to the same object it seems)

--- new code after reading the replies -

   public int[] bk(List<Integer> r, List<Integer> p, List<Integer> x) {
    int count[] = new int[n];
    int u = 1;

    List<Integer> tempPX = new ArrayList<Integer>();
    List<Integer> newR, newP, newX;

    if (p.isEmpty() && x.isEmpty()) {
        count[r.size()]++;
    } else {

        // find vertex with largest degree in P U X        
        tempPX.addAll(p); 
        tempPX.addAll(x);
        for (Integer v : tempPX) {            
            if (neighbours[v].size() > neighbours[u].size()) {
                u = v; 
            }
        } 

        p.removeAll(neighbours[u]);  // P \ neighbours[u]
        newP = new ArrayList<Integer>(p); 
        for (Integer v : newP) {

            r.add(v); // R U  v
            newR = new ArrayList<Integer>(r);

            p.retainAll(neighbours[v]);  // P /\ neighbours[v]
            newP = new ArrayList<Integer>(p);

            x.retainAll(neighbours[v]); // X /\ neighbours[v]
            newX = new ArrayList<Integer>(x);

            bk(newR, newP, newX); 

            p.remove(v); // removing object
            x.add(v); // X U v
        }

    }

    return count;
}

Answer 1

ArrayList newP = P;

This only creates a second reference to the same ArrayList. To copy the arraylist use

ArrayList newP = new ArrayList(P);

Answer 2

As you've identified, you're copying the reference, not the list. You need to instantiate a new ArrayList object with the entries in the old list.

e.g.

List<Integer> newList = new ArrayList<Integer>(oldList);

So this explicitly creates a new object containing references to the same elements.

Note as an aside that I pass around a reference to the interface List rather than the implementation - generally good practise since you're not exposing implementation throughout the codebase.

Answer 3

Your first && check is redundant, originally the check was with the X argument?

Also, your for loop at the start of the else block doesn't make any sense, what are you trying to do there? The thing is that you are both using a counter (c) and the contents of the tempPX list (v). You use v to do the check but c as the assignment. The result is totally dependent on data ordering and doesn't produce anything meaningful.

Normally you'd use one or the other and use it both in the check and the assignment.

if (p.isEmpty() && p.isEmpty()) {
  count[r.size()]++;
} else {
  u = 0; c = 0; // find vertex with largest degree
  tempPX.addAll(p); tempPX.addAll(x); // P U X
  for (Integer v : tempPX) {
    if (neighbours[v].size() > neighbours[u].size()) {
      u = c; 
    }
    c++;
  }

Either your goal is to find the index in the temppx list with the largest amount of neighbours (drop the c variable and the c++ line, use v in the assignment) OR to just find the index with the largest amount of neighbours without any restriction on the index, in that case you would use a for loop like this:

for (int c = 0; c < neighbours.size(); ++c)

and drop any mention of the temppx list. My guess is your trying to do the first case.