[Boost-users] trouble with large graphs

From: Sebastian Weber (sebastian.weber_at_[hidden])
Date: 2004-11-17 03:04:44

Hi!

I am trying to use the BGL to create random graphs with 10^6 nodes and 
approximetly 10^12 edges. My system is:

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. 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;

The basic program layout is:

typedef adjacency_matrix< undirectedS > graph_t;

int main(int, char*[])
{
   // number of vertices
   const std::size_t vertices = int(1e5);
   // probability of a connection between two vertices
   const double pc = 0.3;
   // yielding number of edges to be distributed randomly
   const std::size_t edges = int(pc * vertices * (vertices - 1) / 2);

   std::size_t i = 0;
   while(i++ < edges) {
     if ((i % int(1e5)) == 0)
       cout << "Inserting edge no. " << i << "; completed " \\
           << (double(i)/double(edges)) * 100.0 << "% ..." << endl;
     graph_t::edge_descriptor e;
     bool inserted = false;
     do {
       graph_t::vertex_descriptor a = rand_gen(), b;
       do {
        b = rand_gen();
       } while (a == b);
       tie(e, inserted) = add_edge(a, b, g);
       // if insert fails, then this link already exist -> redo!
     } while(!inserted);
   }

}

Any help would be really appreciated.

Thanks in advance!

Greetings,

Sebastian