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: Jeremy Kawahara (jeremy.kawahara_at_[hidden])
Date: 2012-09-22 23:51:51

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.

Thanks again!
- Jeremy