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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-09-23 12:23:43

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