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

and, since you are in a cluster, you could also try the distributed (parallel) version of SSSP. It will probably boost your running time. About your memory usage, let's see. You have ~580,000,000 edges, 2 fixed point of 4 bytes (vertex indices) plus one floating point of 8 bytes (edge cost) per edge, totalizing ~9.3 GB. If your graph is undirected, but if you use a directed CSR, than you multiply this by 2 (to include both senses), totalizing ~19GB. Now if your 35GB takes into account only the Boost graph size, it would seem a little too much, however if you also consider your own structure to load your information on RAM, it is just fine. leo Le 23/09/2012 18:23, Jeremiah Willcock a écrit :

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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users