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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-04-11 14:23:11

On Apr 11, 2006, at 1:46 PM, Sebastian Weber wrote:

> Hi!
>
>> 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.
>
> When will this stuff be released?

It'll be a part of Boost 1.34.0. No solid date on when that will be  
released. Of course, you can grab the code straight out of Boost CVS.

> What do you mean by less flexible

You need to order the edges by their source vertex when adding them,  
and at present it only supports directed graphs.

> and
> what graph sizes are manageable with this kind of graph on a 32-bit
> machine with sparse graph as <k>=3 ?? 1e8, 1e9 ??

If you're okay with only storing 2B vertices but need > 2B edges, you  
can crunch a graph into 8 bytes per vertex and 4 bytes per edge. With  
< 2B edges, you can knock that down to 4 bytes per edge.

> Sorry for beeing so curious. But anyway: How does this
> compressed_sparse_row_graph thing work?

There is some documentation about the actual format here:

   http://www.boost-consulting.com/boost/libs/graph/doc/ 
compressed_sparse_row.html

        Doug