[boost] [BGL] Multithread problem inserting edges and exploring the same graph

Subject: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-09-15 08:14:24

Hi to all,

I've a problem on BGL. My environment is WinXP, Visual Studio 2005, 
Boost 1.37.

I'm trying to use BGL in the following way. I've a single graph in my 
application, that is an adjacency_list< vecS, vecS, ... >, and I've 2 
kind of threads that work on the graph:
- some "Explorer" threads, that executes a Dijkstra's algorithm repeatedly;
- some "Integrator" thread, that call the add_edge() function repeatedly.

The program often crashes, because it cannot dereference some graph 
elements, some auto_ptr... The crash isn't sistematic, so I think 
there's a concurrency problem. I think that the problem is in the use of 
the vectors in the implementation of the graph. In general, if I've an 
iterator 'it' that point on an vector's element A, and I insert another 
element B before A, then the iterator is now invalid. I suppose that it 
happens something of similar in the graph. If I read the out-edge list 
of a vertex at the same time that I add another out-edge to the same 
vertex, the reading may be inconsistent.

So I've tried with an adjacency_list< listS, vecS, ... >, because if I 
add an element to a list, the previous reference are still valid, but 
I've experienced the same problem again.

If what I've said is correct, then I think that with an adjacency_matrix 
I will not have problems, but I've approximately 5 millions of vertices, 
and the graph is sparse. I think that is a waste of memory. And what 
about the exploring time?

Another question: if I launch *only* a set of Explorer thread, it seems 
that there aren't problems with EdgeList = listS and EdgeList = vecS too.
Can someone confirm to me that the exploring algorithms, like Dijkstra, 
don't modify the graph structure?
Are they read-only algorithms?
Can I safely launch multiple exploration threads simultaneously?

Can someone help me?

Many thanks in advance,
Cosimo Calabrese.