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

Subject: Re: [Boost-users] CSR graph and Dijkstra's to lower graph memory
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-09-23 15:29:17

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 
>> <jewillco_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users