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: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-09-22 16:29:52

I've forgot a pair of questions:

 > Now the solution I propose, since you have a monotonically increasing
 > edge set you can actually compute an incremental solution to the SSSP
 > problem rather than completely re-running Dijkstra.  Basically you can
 > patch up the SSSP solution when you do the edge addition in O(N) time
 > (expected time should be much lower but depends on parameters of your
 > graph that I don't have so I won't try to explain in detail).  Either
 > way this is either somewhat better, or much better than O(N log N) to
 > re-run Dijkstra.  All you do is push the new weight onto the Dijkstra
 > queue and run Dijkstra as normal.
 >

How can I push a weight, if the queue is a vertex queue?

 > [...] If you really do need concurrent
> access to the adjacency list then I'd just wrap a readers-writers lock 
> around each vertex's adjacencies.
> 

How can I implement a lock like this? I must to hack the BGL? Or just 
need to derive from adjacency_list and apply this additional function?

Thanks,
Cosimo Calabrese.