|
Boost Users : |
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
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net