3

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()
CthenB
  • 800
  • 6
  • 17
  • 1
    try using an iterator for your loops – Martin Golpashin Jan 24 '14 at 15:59
  • 1
    You *are* in fact modifying what you're iterating over. – Dan Getz Jan 24 '14 at 15:59
  • @DanGetz is right. You cannot do visitedFields.add( posNeighbor ); while iterating like this over visitedFields – Martin Golpashin Jan 24 '14 at 16:01
  • nor can you `unvisitedFields.remove( unvisited );` – Silly Freak Jan 24 '14 at 16:04
  • @DAnGetz , I am modifying the results of the loop, but shouldn't it error on my actual .remove / .add code instead of on the loop itself? MartinGolpashin, will changing the loop to use of an iterator fix the issue, or do I need to look at another construct? – CthenB Jan 24 '14 at 16:08
  • your `for` loops are translated into code using `Iterator`s. `Iterator`s don't have a "finished" method to tell the `Collection` that it can allow modification again. So, the exception is thrown on `Iterator.next()`. – Dan Getz Jan 24 '14 at 16:15
  • This is not Dijkstra's algorithm, it's simple BFS. – Niklas B. Jan 24 '14 at 16:24
  • @Chrotenise, What are you intending to do by `visitedFields.add( posNeighbor )`? Isn't it already in there? – Dan Getz Jan 24 '14 at 16:33
  • @DanGetz You're correct. I'm trying to add the wrong value. – CthenB Jan 24 '14 at 16:36
  • @NiklasB alright, thanks for pointing that out. I started with the intention of implementing Dijkstra, but in the way it is described to check all neighbors, I chose to edit things a bit. – CthenB Jan 24 '14 at 16:37
  • @Chrotenise the point is that Dijkstra works on weighted graphs and therefore needs a priority queue. It's fine to use BFS here, since the edge weights are all the same. Just keep that in mind :) – Niklas B. Jan 24 '14 at 16:42
  • Possible duplicate of [Iterating through a Collection, avoiding ConcurrentModificationException when removing in loop](http://stackoverflow.com/questions/223918/iterating-through-a-collection-avoiding-concurrentmodificationexception-when-re) – Raedwald Mar 28 '16 at 14:35

3 Answers3

4

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.

axiopisty
  • 4,972
  • 8
  • 44
  • 73
  • I chose you as the answer, because you both gave the same documentation and you gave a code example. +1 for both of you, though. – CthenB Jan 24 '14 at 16:26
3

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.

Community
  • 1
  • 1
jalopaba
  • 8,039
  • 2
  • 44
  • 57
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)

Marco13
  • 53,703
  • 9
  • 80
  • 159