[Boost-users] Re: trouble with large graphs

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-11-17 03:29:07

Sebastian Weber wrote:

> Hi!
> 
> 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 about 2^3^12 = 2^(3*12) = 2^36 edges, which looks more that 32 bit
processors can address.

> Debian Sarge with Kernel 2.6.8 on a Pentium M 1.6GHz with 1 Gig of RAM
> g++-3.4.2
> boost 1.32.0 latest draft tarballs
> I am not using the STL libaries from SGI, but the standard libstdc++6
> 
> My first shot with the adjacency_list ate all my main memory. Which
> isn't really surprising. But adjacency_matrix failed also when I passed
> 10^5 nodes. 

Adjacency matrix requires 10^5^2 = 10^10 = 2^3^10 = 2^(30) bytes, I think.

> Running the program within gdb gives me at least the 
> following error message:
> 
> 0x080c0fec in boost::detail::get_edge_exists<char> \\
> (edge_proxy=@0x73fbdc28) at adjacency_matrix.hpp:84
> 84            return edge_proxy;

That's not an error message ;-)

> Any help would be really appreciated.

It looks like you should either get 64 bit processor with many gig of
memory, or use some other approach.

- Volodya