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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-09-22 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, thread-specific 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, thread-specific 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