'std::bad_alloc' and Graph recursion problem

[andra]

Hi All,
I would like to build a graph of words and be able to traverse on such a graph. I have written the following piece of code to do that:


map<string, map<string,graphNode> > graph;
vector <string> all_paths;

void Graph::add(string first, string second, double weight){
map<string, map<string,graphNode> >::iterator p;
p = graph.find(first);
if(p != graph.end()) {
map<string, graphNode> gNode = graph[first];
graphNode f2;
f2.name = second;
f2.weight = weight;
f2.status =0;
gNode.insert(make_pair(second,f2));
graph.erase(first);
graph.insert(make_pair(first,gNode));
}
else{
graphNode f2;
f2.name = second;
f2.weight = weight;
f2.status = 0;
map<string, graphNode> gNode;
gNode.insert(make_pair(second,f2));
graph.insert(make_pair(first,gNode));
}
}


int Graph::allPaths(graphNode &v, graphNode &w,vector<string> visited){
visited.push_back(v.name);
if ((v.name).compare(w.name)==0){
string str = vectorToString(visited);
all_paths.push_back(str);
return 1;
}
else{
map<string, map<string, graphNode> >::iterator pos;
pos = graph.find(v.name);
if(pos != graph.end()) {
map<string, graphNode> pn = pos->second;
map<string, graphNode>::iterator p = pn.begin();
while(p != pn.end()) {
string name = p->first;
vector<string>::iterator it;
it = find(visited.begin() , visited.end() , name);
if (it!=visited.end()) {
} //if
else{
allPaths(p->second,w,visited);
}
p++;
} //while
return 0;
} //if
else{
cout << v.name << " does not exists in the graph \n ";
}
} //else
}




I have about 510096 nodes in the graph and when I call the all_paths method, I get the following error:
terminate called after throwing an instance of 'std::bad_alloc'
I am not sure why this is happening? Could you help me with that?


One thing that I noticed is that some parts of the graph are not connected, as a result when I reach the leaf of the graph, it enters this part of the code "cout << v.name << " does not exists in the graph \n "; and I am not sure if the recursive part of the code can still handle such a situation or not. Do you have any suggestions for this part?

Thanks a lot,
Andra

[helios]

You're probably out of memory. At only 4 bytes per node, half a million nodes need 2 GiB, not counting dynamic allocation overhead.

[andra]

Thanks. Is there any way that I can overcome the memory problem?

Andra

[helios]

If installing more memory is not an option, you'll have to keep most of the structure in your file system. If you're using a 32-bit OS, you can't use std::fstream or the C file interface, since they're limited to seeking only within the first 2 GiB (2^31-1 bytes, to be exact).