Edge reversing on directed graph

Question

I have a directed graph implemented with the adjacency lists using a Java HashMap. Graph class stores only a pointer like this:

HashMap<Node<V>, List<Edge<V>>> graph;

I'm trying to write a method that can perform a transposition of the graph (by side effect). Here is the code:

/**
 * Helper method for connection test 
 */
public void reverseDirection(){
    for(Node<V> v : getNodes()){
        for(Edge<V> e : getOutEdges(v)){
            Node<V> target = e.getTarget();
            int weight = e.getWeight();
            graph.get(v).remove(e);
            graph.get(target).add(new Edge<V>(v, weight));
        }
    }
}

While executing some tests i get this:

 Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:953)
    at java.util.LinkedList$ListItr.next(LinkedList.java:886)
    at esercitazione9.Graph.reverseDirection(Graph.java:71)
    at esercitazione9.GraphUtil.fortementeConnesso(GraphUtil.java:126)
    at esercitazione9.GraphUtil.main(GraphUtil.java:194)

Javadoc says that this exception does not always indicates that an object has been concurrently modified. It may occurs even when a thread modifies a collection directly while it is iterating over the collection.

This is exactly my case, but I have no ideas to solve it. There is another way to reverse all the edges directions without having iterator-collection interference? Note: computational cost can't be above O(n+m).

Answer 1

You cannot remove item from the collection you iterate over in any other way than using the iterator's remove() method (well, unless it's ConcurrentHashMap, I cannot think other exceptios at the moment). There are two canonical solutions to this problem:

1. Rewrite your loops to use explicit Iterators and call remove instead of graph.get(v).remove(e);

2. Create a separate collection to hold items to remove (or, alternatively, items to retain) from the collection you iterate over, and do it after the actual iteration.

As you explicitly ask for "not 1", I believe it is the only option. Computational cost should not increase if you store items to remove, as the number of allocations and insertions cannot be larger than O(n+m) (n collections, m removed edges total). Keep in mind that in case your graph contains loops, special care must be taken.

Answer 2

Ok. I just modified the code as suggested:

public void reverseDirection(){
    Collection<Edge<V>> removed = new LinkedList<Edge<V>>();
    for(Node<V> v : getNodes()){
        for(Edge<V> e : getOutEdges(v)){
            Node<V> target = e.getTarget();
            int weight = e.getWeight();
            removed.add(e);
            graph.get(target).add(new Edge<V>(v, weight));
        }
        graph.get(v).removeAll(removed);
    }
}

I think now there are some issues with the logic of the algorithm because doesn't return the expected result. I will post the fixed code later.