Java: How do handle ConcurrentModificationException in this particular situation?

Question

Before I posted this question, I read the post in here. But for this particular problem, I really do not know how I can apply the same philosophy ?

In the following problem, my variable graph has the following structure: HashMap<Integer, ArrayList<Integer>>. And u and v has type int. Basically, I want to remove the value v in the arraylists with a key value of i, where i appears in the arraylist of v.

So, if the integer i appears in the arraylist of v, we get the arraylist of i in the graph and remove the value v from it.

This sounds really complicated. But I am stuck at this ConcurrentModificationException for some time now.

public int random_contraction_algo(){
    while(graph.size() > 2){
        int u = select_remaining_edges_at_random(new ArrayList<Integer> (graph.keySet()));
        int v = select_remaining_edges_at_random(graph.get(u));      
        merge(u,v);        
    }
    return -1;
}

// select a pair of vertices from an edge
public int select_remaining_edges_at_random(ArrayList<Integer> vertices){
    int index = (int)(Math.random() * (vertices.size()));
    return vertices.get(index);
}

public void merge(int u, int v){

    graph.get(u).addAll(graph.get(v));

    // remove self-loops
    graph.get(u).removeAll(Collections.singleton(u));
    graph.get(u).removeAll(Collections.singleton(v));

    // make sure all the edges of v are connected to u instead v
    for(Iterator<Integer> iterator = graph.get(v).iterator(); iterator.hasNext();){
        Integer i = iterator.next();
        graph.get(i).remove((Integer) v);
        graph.get(i).add(u);

    }
    // remove key
      graph.remove(v);
}

UPDATE: I really appreciate your answers. However, I realize I forgot to show you guys that there is an outer loop in my code.

I tried implementing your solutions but the ConcurrentModificationException still occurs.

These are the error messagaes:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:886)
    at java.util.ArrayList$Itr.next(ArrayList.java:836)
    at HashMapOfArrayList.merge(ArraylistOfArrayList.java:96)
    at HashMapOfArrayList.random_contraction_algo(ArraylistOfArrayList.java:69)
    at RunAlgo.main(ArraylistOfArrayList.java:111)

I don't think this will be a problem, except when i == v, but then you can just use the standard iterator approach. — Ordous, Dec 10 '14 at 17:00
Modifying other lists in the loop cannot be a problem. If you are still getting the exception with either of two solutions below, it is caused by some code you have not included into your post. @Ordous' solution might also fail, if you have the same list stored in the map under a different key. Mine is immune to that (but is slightly less efficient, since it involves one addition scan of the list). — Dima, Dec 10 '14 at 17:22
I will edit this question again because I want to show you guys more code, which involves an outer loop. Please See UPDATE — mynameisJEFF, Dec 10 '14 at 17:29
@mynameisJEFF Is there any possibility you can give a small data example that fails? Like 2-3 nodes with edges? I've tried this with 3 nodes each connected to each other and it worked fine (and threw an exception if explicit self-loop removal is absent) — Ordous, Dec 10 '14 at 17:56
My bad. There is a self-loop in my code, which is why the expcetion is thrown. Sorry about this. — mynameisJEFF, Dec 10 '14 at 18:06

score 3 · Answer 1 · answered Dec 10 '14 at 17:06

3

The problem is that when v == i, you are modifying the same list as you are iterating over.

A simple solution is to guard for this condition:

for(Iterator<Integer> it = graph.get(v).iterator(); it.hasNext();) {
    Integer i = it.next();
    if (i == v) {
        it.remove();
    } else {
        graph.get(i).remove((Integer) v);
    }
}

answered Dec 10 '14 at 17:06

Ordous

3,844
15
25

This code can also cause a concurrent modification exception since you are accessing the Map will using the Iterator. – markbernard Dec 10 '14 at 17:08
@markbernard Accessing is fine, modifying is not. And the map is not modified here or in the question. – Ordous Dec 10 '14 at 17:09
this doesn't work. Because graph.get(i) is another arraylist in the hashmap, and if I try to remove an item from the arraylist `i`, then I am modifying the map. – mynameisJEFF Dec 10 '14 at 17:16
@mynameisJEFF If you're modifying an array list, you're modifying an array list, not the map. Unless there is an outer iteration that you haven't shown and that involves the lists again - this should be OK. – Ordous Dec 10 '14 at 17:18
There is another outer while loop but I am only performing operations like: `graph.remove(v)`. I probably need to post a new question then. – mynameisJEFF Dec 10 '14 at 17:26
If the `graph.remove(v)` is done while iterating over a `HashMap` you'll also get a CME. Is the CME actually thrown from an ArrayList, or from a HashMap? Also note @Dima's comment - he is correct that my solution will not work if you have the same list under multiple keys (you should use his approach then). – Ordous Dec 10 '14 at 17:29

Dima · Answer 2 · 2014-12-10T17:10:24.337

2

Remove v explicitly from the list before the loop: graph.get(v).remove(v)

List<Integer> list = graph.get(v);
list.remove(v);
for(Integer i: list){
   graph.get(i).remove(v)
}

edited Dec 10 '14 at 17:10

answered Dec 10 '14 at 17:02

Dima

39,570
6
44
70

Dima Maligin · Accepted Answer · 2014-12-10T18:11:23.070

I may have misunderstood you. But if you ment

So, if the integer i appears in the arraylist of v, we get the arraylist of i in the graph and remove the value v from it.

Is this what you want to do?

HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < 100; i++) {
    graph.put(i, new ArrayList<Integer>());
}

int i = 0; // change value to whatever
int v = 0; // change value to whatever
if (graph.get(v).contains(i)) {
    graph.get(i).remove(new Integer(v));
}

If it's not can you try to explain exactly what you need.

EDIT:

I think this should work:

HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < 100; i++) {
    graph.put(i, new ArrayList<Integer>());
}

int v = 0; // change value to whatever
int u = 0;
ArrayList<Integer> list = new ArrayList<Integer>(graph.get(v));
for(Integer i : list){
    if(graph.get(i).contains(v)){
        graph.get(i).remove(new Integer(v));
        graph.get(i).add(u);
    }
}

This creates a copy of the ArrayList in question thus we never iterate on the Map itself making the edits to the Map possible.

Tell me if it works.

Yes. But there is now an additional step that I want to do. See the explanation: There is an loop that go through each element of the arraylist of `v`. For each element `i` in the arraylist of `v`, I use it as a key to grep its corresponding arraylist in the same hashmap. And if the arraylist of `i` contains the value `v`, I want to remove it and add a new integer `u` to the arraylist of `i`. (Note that `i` and `v` will never be the same). — mynameisJEFF, Dec 10 '14 at 17:54
@mynameisJEFF I edited the answer(haven't ran it though) so check if it works for you. — Dima Maligin, Dec 10 '14 at 18:06

Java: How do handle ConcurrentModificationException in this particular situation?

3 Answers3