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

Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Herve Bronnimann (hervebronnimann_at_[hidden])
Date: 2009-09-15 09:31:43

Cosimo: if you've got one thread that reads and one that modifies your  
adjacency list, you must protect your graph with a (per vertex)  
Mutex.  If you insist that you are not accessing the same edges at the  
same time, you still must. If you insist you are not accessing the adj  
lists at the same time, then maybe (but I doubt you can make that  
guarantee and the fact you crash means that you probably aren't).

If you go all listS (both tmpl args) you still must use a mutex unless  
you somehow hack BGL to use lockfree lists. I doubt anyone has ever  
done that.

You seem to think the crash is because of invalidation of iterators.  
It isn't. It's because of the lack of synchronization between your  
threads.

HB

Sent from my iPhone

On Sep 15, 2009, at 8:14 AM, Cosimo Calabrese <cosimo.calabrese_at_[hidden] 
 > wrote:

> 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.
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost