Boost logo

Boost :

Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-09-17 09:46:33

Herve Bronnimann ha scritto:
> 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.

Hi Herve,

Thanks for your contribute, but I'm not sure I understand what you've
said: each vertex must have a mutex?

So, I'm trying to implementing a sync_adjacency_list module, a graph
adaptor similar to filtered_graph and reverse_graph; I've reimplemented
every function required by the concepts modeled by the adjacency_list;
each function has synchronized with the others by the same mutex, so
every function that works on a sync_adjacency_list is atomic.
I've implemented every graph traversal concept without problems, like this:

template <typename G>
typename sync_adjacency_list<G>::edges_size_type
num_edges(const sync_adjacency_list<G>& g)
   lock( sync_adjacency_list_mutex );
   return num_edges(g.m_g);

Now I'm trying to implement the EdgeMutableGraph concept, in order to
obtain the add_edge() support, but I've a problem.

template <typename G>
std::pair<typename sync_adjacency_list<G>::edge_descriptor, bool>
add_edge(const typename sync_adjacency_list<G>::vertex_descriptor u,
          const typename sync_adjacency_list<G>::vertex_descriptor v,
          const sync_adjacency_list<G>& g)
   lock( sync_adjacency_list_mutex );
   return add_edge(u, v, g.m_g);

When I try to use it with G = adjacency_list< listS, vecS, directedS,
vertexs_properties, edges_properties >, I'm obtaining the follow compile
error message:

"error C2665: 'boost::add_edge' : none of the 2 overloads could convert
all the argument types"

It seems that the compiler can't find the right implementation of
add_edge(). It's strange, because I'm sure that the add_edge() exists
for adjacency_list<...>. The add_edge() version I've implementated is
only a wrapper of it.

Where I'm wrong? Is it a MSVC 2005 function resolution bug?

Thanks in advance,
Cosimo Calabrese.

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