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-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?

Cosimo Calabrese.

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