ConcurrentModificationException while trying to implement Dijkstra algorithm

Question

I'm trying to implement Dijkstra's shortest path algorithm in my maze. ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm )

I got two HashSets, one for visited and one for unvisited fields. Once a field has been visited by all its neighbors through the algorithm, I want to put it in the visited map and remove it from the unvisited.

However, when I try to run the algorithm I get a ConcurrentModificationException in Netbeans.

Funny thing is - I've read up on the problem and from what I understand, this issue comes forth from trying to manipulate / remove data from the Set, not from iterating over it. However, I get the error on an iteration of the set, namely:

for( Field unvisited : unvisitedFields ) {

Since I got time issues, a work-around for the issue would suffice but if I'm using bad practice, I'd love to know what a better approach to solving this problem would be. Full code of method below, unvisitedFields is initialized as a class variable but has same parameters as visitedFields. Reason for it being a class variable is because I fill it at the top of my class, together with a 2D array.

public void calculcateSPath(Field curLocation , Field target ) {

        Set<Field> visitedFields = new HashSet<>();
        ArrayList<Field> shortestPath = new ArrayList<>();

        shortestPath.add( target );
        curLocation .setDistance( 0 );
        unvisitedFields.remove( curLocation  );
        visitedFields.add( curLocation  );

        // until all fields have a corresponding value to field, it continues searching.
        while( unvisitedFields.isEmpty() == false ) {

            // iterate through the Set containing all unvisited fields.
            for( Field unvisited : unvisitedFields ) {

                //iterate through the Set containing all visited fields.
                for( Field posNeighbor : visitedFields ) {

                    // if the unvisited field has a visited field as neighbor
                    if( unvisited.allNeighbors().containsValue( posNeighbor )) {

                        // check if the wall between them is down
                        if(( unvisited.getNeighbor( Direction.up ).equals( posNeighbor ) && posNeighbor.drawDown() == false )
                            || ( unvisited.getNeighbor( Direction.right ).equals( posNeighbor ) && unvisited.drawRight() == false )
                            || ( unvisited.getNeighbor( Direction.down ).equals( posNeighbor ) && unvisited.drawDown() == false )
                            || ( unvisited.getNeighbor( Direction.left ).equals( posNeighbor ) && posNeighbor.drawRight() == false )) {

                            visitedFields.add( posNeighbor );

                            // if so, check if the current distance is smaller than the previous distance.
                            if( unvisited.getDistance() > ( posNeighbor.getDistance()+1 ) ) {

                                // assign the new shorter distance and the connection point
                                unvisited.setDistance( posNeighbor.getDistance() + 1 );
                                unvisited.setVisitedNeighbors( 1 );
                                unvisited.setPrevious( posNeighbor );

                            }
                        // if not, add a count to the visited neighbors    
                        } else {

                            unvisited.setVisitedNeighbors( 1 );

                        }

                        //if all neighbors have been visited, remove the field from the unvisited list and add to visited.
                        if( unvisited.getVisitedNeighbors() == unvisited.allNeighbors().size() ) {

                            unvisitedFields.remove( unvisited );
                            visitedFields.add( posNeighbor );

                        }
                    }
                }
            }
        }

    } // ends calculateSPath()

Answer 1

From the API:

The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

This means that if you want to modify the collection while iterating over it you must use the iterator.remove() method. Rather than using a for each loop, try something like this:

Collection items = ...
Iterator itr = items.iterator();
while(itr.hasNext()) {
  Object o = itr.next();
  boolean condition = ...
  if(condition) {
    itr.remove();
  }
}

Or if you can (and would prefer to) make the modification after the iteration is complete you can do something like this:

Collection items = ...
Collection itemsToRemove = ...
for (Object item : items) {
  boolean condition = ...
  if (condition) {
    itemsToRemove.add(item);
  }
}
items.removeAll(itemsToRemove);

If your collection is of type List, then you can get a ListIterator by invoking listIterator(). A ListIterator augments Iterator by adding methods which allow traversing the list bidirectionally and allows modifying the collection by adding and removing items, or replacing the current item.

Answer 2

When using the "for each" loop in java, you are actually using an Iterator under the hoods. See Which is more efficient, a for-each loop, or an iterator?.

Since you are modifying the underlying collection (remove) without using the add or remove method of the iterator, you are getting a ConcurrentModificationException because java collections are fail-fast:

An iterator is considered fail-fast if it throws a ConcurrentModificationException under either of the following two conditions:

1. In multithreaded processing: if one thread is trying to modify a Collection while another thread is iterating over it.

2. In single-threaded or in multithreaded processing: if after the creation of the Iterator, the container is modified at any time by any method other than the Iterator's own remove or add methods.

So you have to use an Iterator explicitly, invoking remove on the Iterator instead of the collection.

Answer 3

A general hint: The ConcurrentModificationException can in many cases be avoided by converting the pattern

for (Element element : collection)
{
    if (someCondition) collection.remove(element); // Causes Exception!
}

into a pattern like

Set<Element> toRemove = new HashSet<Element>(); // Or a list
for (Element element : collection)
{
    if (someCondition) toRemove.add(element);
}
collection.removeAll(toRemove);

This is often more convenient and easier to understand than explicitly dealing with the Iterator. It might also be applicable in your case (although, admittedly, did not fully follow your code into the highest nesting depth)