Boost logo

Boost :

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at