Menu

#178 DijkstraDistance can crash JVM in cached mode

closed-invalid
nobody
5
2012-05-09
2012-05-09
tel
No

SYNOPSIS:
When the DijkstraDistance object works in cached mode (default behavior), as DistanceMaps are cached from different vertices, the object can grow very large and eventually crash JVM as more vertices are added. In addition, the computation time for additional vertices increases a lot. This can be a frequent case when distances must be calculated between all vertices in large graphs.

SAMPLE FIX/WORKAROUND:
Use Dijkstra distance object in non-cached mode, although it would be preferable that the object can more efficiently manage its internal state so that it can be used in cached mode in large graphs

Discussion

  • Joshua O'Madadhain

    This isn't surprising, and that's why caching is an option. If you think about it, the amount of space required goes up as O(mn) (O(m) space for each of O(n) start vertices). If you need to keep all of those distances, you'll need a lot of memory. If you don't, then don't use caching.

     
  • Joshua O'Madadhain

    • status: open --> closed-invalid
     

Log in to post a comment.