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