Re: [Boost-users] trouble with large graphs

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-17 11:07:09

On Nov 17, 2004, at 3:04 AM, Sebastian Weber wrote:
> I am trying to use the BGL to create random graphs with 10^6 nodes and 
> approximetly 10^12 edges. My system is:

That's a _really_ dense graph.

An adjacency matrix is clearly the right representation for it, but 
note that with ~10^12 edges you're on the scale of a terabyte. Unless 
you have way more memory that I, you'll need to distribute the graph 
across a whole bunch of computers. We've been going in this direction 
for our own research into the Parallel BGL, but have focused only on 
sparse graphs with a distributed adjacency_list, so we won't be much 
help at the moment :(.

If you can, your best bet is to scale back the problem size 
dramatically. You might be able to reduce the memory requirements of 
adjacency_matrix a bit by allowing it to use a vector<bool> instead of 
a vector<char>.

        Doug