Re: [Boost-users] High memory requirement of adjacency_list

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-12 11:16:06

On Apr 12, 2006, at 5:01 AM, Pratyush wrote:

>>> The graph populated is taking about 190MB of memory, i.e., 32 bytes/
>>> vertex approx. I was expecting it to take 4 bytes/vertex.
>>
>> That does sound high... are you using a 32- or 64-bit platform? Each
>> vertex needs to store a vector, which is typically 3 pointers (12 or
>> 24 bytes, depending on platform).
>
> I should have been specific about the machine that I was using. I  
> used 64-bit
> platform. That explains 24 bytes out of 32 bytes. I am not clear  
> about the
> remaining 8 bytes.

Neither am I. It's *possible* that the vector has some extra data in  
it (say, something for the allocator?) that is taking up the extra 8  
bytes. What is sizeof(vector<some_user_defined_class_type>) on your  
platform?

> Maybe, instead of vecS as OutEdgeList, I should be using listS (or  
> slistS) if
> number of out edges per vertex is less, say, 2 or 3.

A list typically uses 2 pointers; I'm not sure about slist.

>> The next release of the Graph library will have the
>> compressed_sparse_row_graph graph type, which requires much less
>> memory than adjacency_list. Naturally, it's also less flexible.
>
> That's good news! I am eagerly looking for the next release.

You can always grab the compressed_sparse_row.hpp header from Boost  
CVS. It isn't likely to change before the release, unless someone  
finds a problem with it.

        Doug