Re: [Boost-users] [BGL] reducing memory requirements for adjacency list

Subject: Re: [Boost-users] [BGL] reducing memory requirements for adjacency list
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-09-01 13:13:01

On Tue, 1 Sep 2009, Soeren Meyer-Eppler wrote:

>> One issue with my last reply: I didn't see that you were using a
>> bidirectional graph type.  The CSR graph does not support bidirectional
>> graphs currently; I can put that together or describe how to do it if
>> you want (with the graph structure being about 3x as large, but not
>> duplicating the properties).  That might be your best option.
>
> Yes, I absolutely require bi-directional graphs. As I mentioned, the
> application is static code analysis and a callgraph is inherently
> bi-directional. So yes, I'd really like to know how to use the CSR
> graph in a bidirectional manner.

OK.  I would suggest creating a wrapper class that contains a CSR graph, 
an index vector (similar to m_rowstart in the CSR graph but containing 
start indices for each target), and a vector of edge indices ordered by 
target.  You should easily be able to wrap that up to match the 
bidirectional graph interfaces.  If you would not like to do that 
yourself, please file a Trac ticket requesting the feature.

>> With CSR, the overhead for the properties is just the space the
>> raw data takes up.
>
> Does that mean raw data gets allocated per vertex/edge or in one big
> buffer indexed by vertex/edge? I'd prefer the later of course. I
> need to get the number of small memory allocations down to an
> absolute minimum (i.e. calls to new/mallow with only a few bytes).

The latter; there is a vector of vertex properties and a vector of edge 
properties, each indexed by the numbers of the corresponding objects.

-- Jeremiah Willcock