Graphhopper Dijkstra Ошибка памяти одного-ко-многим

Question

Независимо от размера графика и используемого сервера, в любое время, когда я пытаюсь выполнить маршрут с помощью алгоритма dijkstra_one_to_many, я переполняю свою кучу. Тестовая среда представляет собой m3.2xlarge с 30 ГБ оперативной памяти и жесткими дисками 2x80gb.

java.lang.OutOfMemoryError: Java heap space

Я разыскал блок кода, который является проблемой внутри com.graphhopper.routing.DijkstraOneToMany в методе findEndNode:

while (true) { 
     visitedNodes++; 
     EdgeIterator iter = outEdgeExplorer.setBaseNode(currNode); 
     while (iter.next()) { 
      int adjNode = iter.getAdjNode(); 
      int prevEdgeId = edgeIds[adjNode]; 
      if (!accept(iter, prevEdgeId)) 
       continue; 

      double tmpWeight = weighting.calcWeight(iter, false, prevEdgeId) + weights[currNode]; 
      if (Double.isInfinite(tmpWeight)) 
       continue; 

      double w = weights[adjNode]; 
      if (w == Double.MAX_VALUE) { 
       parents[adjNode] = currNode; 
       weights[adjNode] = tmpWeight; 
       heap.insert_(tmpWeight, adjNode); 
       changedNodes.add(adjNode); 
       edgeIds[adjNode] = iter.getEdge(); 

      } else if (w > tmpWeight) { 
       parents[adjNode] = currNode; 
       weights[adjNode] = tmpWeight; 
       heap.update_(tmpWeight, adjNode); 
       changedNodes.add(adjNode); 
       edgeIds[adjNode] = iter.getEdge(); 
      } 
     } 

     if (heap.isEmpty() || isMaxVisitedNodesExceeded() || isWeightLimitExceeded()) 
      return NOT_FOUND; 

     // calling just peek and not poll is important if the next query is cached 
     currNode = heap.peek_element(); 
     if (finished()) 
      return currNode; 

     heap.poll_element(); 
} 
``` 

Кажется, никогда не найти конечный узел и структуры внутренних данных (мин куча?) растет, растет и растет, пока не кончится пустое пространство. Почему это происходит?

Я могу опубликовать свои config.properties, если это необходимо. Спасибо, Петр, за то, что собрал потрясающую часть программного обеспечения с открытым исходным кодом.

Answer 1

Класс DijkstraOneToMany в настоящее время не предназначен для использования (легко) извне, например. он не является потокобезопасным. Вы можете переключиться на простой Dijkstra без другого состояния окончания, чтобы снизить требования к памяти для простых случаев.

Это сказал ... там могут быть следующие вопросы:

• убедитесь, что вы кэшировать вызовы DijkstraOneToMany как это создает большие начальные datastructures
• снова: использовать его только из одного потока (например, через ThreadLocal)
• Кажется, что нигде не найти конечный узел -> Может быть, вы используете с ним QueryGraph? Это не будет работать, поскольку мы создаем так называемые виртуальные узлы в QueryGraph, которые DijkstraOneToMany не знает, вместо этого попытайтесь выбрать следующий узел башни, например. через избегая QueryGraph полностью или вручную через EdgeIterator

Спасибо Питеру за составление удивительный кусок программного обеспечения с открытым исходным кодом.

Это был не только я - это сообщество усилий :)!