有向图上的边反转

Question

我有一个有向图，它使用HashMap实现邻接列表。Graph只存储这样的指针：

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

我正在尝试编写一种方法，它可以执行图形的转位(通过副作用)。以下是代码：

/**
 * 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));
        }
    }
}

在执行一些测试时，我得到了以下内容：

 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说，此异常并不总是表示对象已被并发修改。即使当线程在对集合进行迭代时直接修改集合时，也可能发生这种情况。

这完全是我的案子，但我不知道怎么解决。有另一种方法，以扭转所有的边缘方向，而不具有迭代-收集干扰？注意:计算成本不能超过O(n+m)。

Answer 1

除了使用迭代器的remove()方法之外，您不能以任何其他方式从迭代器的集合中删除项(嗯，除非它是ConcurrentHashMap，我现在不能考虑其他例外)。对于这个问题有两种典型的解决方案：

1. 重写循环以使用显式Iterator，并调用remove而不是graph.get(v).remove(e);
2. 创建一个单独的集合，保存要从迭代的集合中删除(或者保留的)项，并在实际迭代之后执行。

既然你明确要求“不是1"，我相信这是唯一的选择。如果存储要删除的项，则计算成本不应增加，因为分配和插入的数量不能大于O(n+m) (n组，m删除边总数)。请记住，如果图中包含循环，则必须特别小心。

Answer 2

好的。我只是按照建议修改了代码：

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);
    }
}

我认为现在算法的逻辑有一些问题，因为没有返回预期的结果。稍后我会把固定的代码发出去。