Реверсирование края по ориентированному графу

Question

У меня есть ориентированный граф, реализованный с помощью списков смежности с использованием 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).

Answer 1

Вы не можете удалить элемент из коллекции, которую вы перебираете любым другим способом, чем с использованием метода итератора remove() (ну, если это не ConcurrentHashMap, я не могу думать о других исключениях на данный момент). Есть два канонических решений этой проблемы:

1. перепишите петлю использовать явные Iterator с и называют remove вместо graph.get(v).remove(e);

2. Создать отдельную коллекцию для хранения предметов для удаления (или, в качестве альтернативы, элементы сохранить) из коллекции, которую вы перебираете, и делать это после фактической итерации.

Поскольку вы явно просите «не 1», я считаю, что это единственный вариант. Вычислительная стоимость не должна увеличиваться, если вы храните элементы для удаления, так как количество распределений и вставок не может быть больше, чем O (n + m) (n коллекций, т удаленных краев всего). Имейте в виду, что в случае, если ваш график содержит циклы, необходимо соблюдать особую осторожность.

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

Я думаю, что сейчас есть некоторые проблемы с логикой алгоритма, поскольку не возвращает ожидаемого результата. Я отправлю фиксированный код позже.