
Boost : 
Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20090922 17:27:17
On Tue, 22 Sep 2009, Cosimo Calabrese wrote:
>
>>
>> 1. When does the shortest paths solution have to be correct (i.e. match the
>> graph exactly)?
>
> Well, I always need the exact solution.
>
>> 2. Are there any constraints as to when your 'integrator' thread can call
>> add_edge() (this relates to 1. pretty directly)
>
> No, there aren't. The add_edge() can be called at any moment.
It looks like (from your description that I snipped out) that you are
really creating a new graph for every thread that is a copy of the
original graph plus some new, threadspecific edges. I would not
recommend having a single graph for all of this because of the issues you
are having. What about the following:
1. Create a union_graph adapter that takes two graphs with the same number
of vertices and merges their edge sets (concatenating the out_edges and
in_edges for each vertex implicitly). Properties would also need to be
handled (or indexes for external properties).
2. For every thread, create a new graph with just that thread's new edges
and run Dijkstra's algorithm on the union_graph of that piece and the
original graph.
3. Throw away the temporary, threadspecific graph when the thread is
done.
That should remove all of your locking (except in the memory allocator),
and the filtered_graph, and greatly simplify (and probably speed up) the
code. Do you think this will work?
 Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk