jgrpht-Floyd Warshall's Algorithm

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

jgrpht-Floyd Warshall's Algorithm

Sandeep Sas
Hi,

I am pretty new to jgrapht. 

I am trying to run all-pairs shortest path Algorithm for the city of Chicago. The data source is OpenStreetMaps and has 100k nodes. I used jgrapht library for creating the graph.  But when I tried to run the Floyd Warshall's Algorithm on the graph, the program existed with error: Insufficient Java heap memory. I ran Dijktra's shorted path on this graph and was successful. I already tried increasing the heap size in the Eclipse IDE. 

How do I deal with this issue?

System Config: 64 bit, 16 GB RAM (Eclipse on Windows)

I really appreciate your reply

Thank you

Sandeep

------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741551&iu=/4140
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: jgrpht-Floyd Warshall's Algorithm

Joris Kinable
You do realize that you are trying to calculate something in the order of 100000^2=10.000.000.000 shortest paths right? Let's assume for the sake of argument that each path can be stored in a single byte (8 bits). This is obviously not realistic since a single integer in java already takes up 4 bytes. Nevertheless, let's assume that you need 1 byte per path. There are 2^30 bytes in a single gigabyte. That means that you would need 
100000^2 /2^30=9.31 Gb. There's no way that your computer with merely 16GB of RAM will be able to keep all paths in memory.

There are a few things you can try however. Create a new Floyd Warshall (FW) instance from your graph and invoke shortestDistance(a,b) for a pair of vertices a,b. If you don't get a cost due to an out-of-memory or simply because it takes too long, you are out of luck. My guess is that this will be the case, as FW runs in cubic time if I recall correctly, which means that you need 100000^3 iterations to actually calculate the distance matrix. If your computer does let's say 10^7 or so iterations per second, that may still take a very long time.

The way FW is implemented in jgrapht is as follows:
1. If you invoke any of the functions in the FW class, it will calculate a next-hop matrix which for any pair of nodes a,b gives you the next node on the shortest path from a to b. This is the core of any FW implementation (see https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm). As an added bonus, you get the distance matrix for free.
2. if you would invoke any other function except shortestDistance(a,b) in the FW class, it will start calculating *every* shortest path between every pair of nodes. This is nice for efficiency since next time you invoke the getShortestPath(a,b) function you'll get the path in constant time, since all the paths are precomputed. The disadvantage ofc is that precomputing all paths is super expensive in terms of memory.

When you invoke shortestDistance(a,b), the FW class only calculates the next0hop matrix, but will not precompute all paths. If this works for you, you can easily write a new function which calculates the shortest path from a to b based on the next-hop matrix. Example code for this is already in the FW class. 

Running Dijksta's shortest path alg for every pair of nodes is a bad idea: this is way slower and more memory intensive than FW.

Joris


On Sun, Nov 22, 2015 at 2:02 PM, Sandeep Sas <[hidden email]> wrote:
Hi,

I am pretty new to jgrapht. 

I am trying to run all-pairs shortest path Algorithm for the city of Chicago. The data source is OpenStreetMaps and has 100k nodes. I used jgrapht library for creating the graph.  But when I tried to run the Floyd Warshall's Algorithm on the graph, the program existed with error: Insufficient Java heap memory. I ran Dijktra's shorted path on this graph and was successful. I already tried increasing the heap size in the Eclipse IDE. 

How do I deal with this issue?

System Config: 64 bit, 16 GB RAM (Eclipse on Windows)

I really appreciate your reply

Thank you

Sandeep

------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741551&iu=/4140
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741551&iu=/4140
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...