[prev in list] [next in list] [prev in thread] [next in thread] 

List:       boost-users
Subject:    Re: [Boost-users] CSR graph and Dijkstra's to lower graph memory
From:       Leo Hidd <leohidd () gmail ! com>
Date:       2012-09-23 19:29:17
Message-ID: 505F630D.10401 () gmail ! com
[Download RAW message or body]

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 =E9crit :
> On Sat, 22 Sep 2012, Jeremy Kawahara wrote:
>
>> On Sat, Sep 22, 2012 at 11:51 AM, Jeremiah Willcock =

>> <jewillco@osl.iu.edu> 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

_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
[prev in list] [next in list] [prev in thread] [next in thread]