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

Subject: [Boost-users] [BGL] reducing memory requirements for adjacency list
From: Soeren Meyer-Eppler (Soeren.Meyer-Eppler_at_[hidden])
Date: 2009-09-01 10:03:25

Hi,

I'm using adjacency_list< vecS, vecS, bidirectionalS ... >
extensively. I have so many graphs loaded at once that memory
becomes an issue. I'm doing static program analysis and store the
callgraph and flowgraphs of the disassembled binary in boost graphs.
Thus I can have several ten thausand functions==flowgraphs and one
gigantic callgraph. I'd really like to reduce memory usage for my
graphs while still using the BGL.

Since my graphs are static after loading and edge and vertex counts
are known beforehand I see huge potential for optimization. For
example, I'd like to allocate a single buffer for all vertices/edges
of a single graph and let the graph just store indices into that buffer.

more questions:
1) what's the memory overhead of using vertex and edge properties? I
have quite a few of them.
2) is it possible to convince the BGL to use the shrink to fit
idiom? As I understand it the adjacency lists use push_back to add
edges. Is it possible to reduce memory usage by swapping the
resulting vector with a copy of itself? Maybe by copying the whole
graph?
3) Is it possible to use boost pool allocators with the BGL? As far
as I can tell the BGL currently performs lots of small allocations -
I'd really like to avoid that for space and runtime efficiency reasons.

Did anyone already build a BGL version optimized for memory usage?
Should I try using the existing graph structures and augment it with
custom allocators or somesuch or is it more fruitful to write my own
implementation and try to stay interface compatible with the BGL so
I may continue to use it's algorithms?

best regards,

    Sören