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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk