
Boost : 
Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 20090922 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 rerunning 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
> rerun 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 readerswriters 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk