Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk