java有向边图的逆
我有一个使用Java 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)
# 1 楼答案
除了使用迭代器的
remove()
方法之外,您无法从迭代的集合中删除项(好吧,除非它是ConcurrentHashMap
,否则我现在不能考虑其他例外情况)。这个问题有两种典型的解决方案:重写循环以使用显式
Iterator
并调用remove
而不是graph.get(v).remove(e);
创建一个单独的集合来保存要从您迭代的集合中删除的项(或者,要保留的项),并在实际迭代后执行此操作
当你明确要求“不是1”时,我相信这是唯一的选择。如果存储要删除的项,则计算成本不应增加,因为分配和插入的数量不能大于O(n+m)(n个集合,总共删除了m个边)。请记住,如果图形包含循环,则必须特别小心
# 2 楼答案
嗯。我只是按照建议修改了代码:
我认为现在算法的逻辑有一些问题,因为它没有返回预期的结果。我稍后会发布固定代码