1

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) を超えることはできません。

4

2 に答える 2

0

Ok。提案どおりにコードを変更しました：

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

期待される結果が返されないため、アルゴリズムのロジックに問題があると思います。修正コードは後ほど載せます。

于 2013-09-10T15:33:08.723 に答える