Re: [Boost-users] CSR graph and Dijkstra's to lower graph memory

On Sat, 22 Sep 2012, Jeremy Kawahara wrote:

On Sat, Sep 22, 2012 at 11:51 AM, Jeremiah Willcock wrote: On Sat, 22 Sep 2012, Leo Hidd wrote:

I'm the OP of that topic. With a great help of Jeremiah WillCock (thank you Jeremiah, you are a great and very patient man :) ), I could finally obtain an working case with CSR graphs (a great amount of messages were sent in private, so they do not appear in the list). Here's an example. Note that I don't provide the the class obj_Mesh, since the only variables I use from it are used to compute the number of edges and the cost of each edge. You can replace these info by your own.

The one thing I would change about the example is not to use &d[0] and &p[0] but to use an iterator_property_map instead (see URL:http://comments.gmane.org/gmane.comp.lib.boost.user/67769); using raw pointers has caused problems for various users in the past.

Thank you so much Jeremiah and Leo! I still need to implement Jeremiah's suggestion but the initial results look very positive.

In case it is of interest to others, after I changed to a CSR graph instead of an adjacency_list, and used the "boost::dijkstra_shortest_paths _no_color_map" instead of the "boost::dijkstra_shortest_paths", both my running time and space requirements significantly dropped.

For a graph with ~3,600,000 nodes and ~580,000,000 edges, after making these changes, my running time went down from about 1.5 hrs to 20 mins and my space requirements went from 95GB to 35 GB.

If you know that you are going to have fewer than 2^32 vertices and/or 2^32 edges, you can also turn down the sizes of the integers used as indices in the graph's representation; see the documentation for details. On a 64-bit machine, they both default to 64 bits, but you can save a lot of storage by reducing their sizes. -- Jeremiah Willcock