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.
It seems a very, very good idea. I like it very much. If it works, I always access to the 'original' graph in read-only modality, that is the only shared object; I don't need to add any vertex or edge to any existing graph, but each thread only needs to create another, completly new graph, which isn't shared with other threads. So the thread explore the union adaptor in read-only modality. Exciting.
Now I must take a look on some 'graph arithmetic'... This adaptor needs only to model the traversal graph concepts. The two graph type in input to the union adaptor must be the same. So all the adaptor types required by the concepts are the same of the input graphs. Now I need a moment to think about the concept funcions (out_edges(), out_degree(), ... ). I'll tell you about the state of the adaptor very soon.
Those should be fairly simple, except that I do not believe Boost.Iterator has a concatenation iterator like the old View Template Library had. If you write a generic concatenate-two-sequences iterator, you might want to consider contributing it to Boost.Iterator. Otherwise, you should just be able to concatenate edge sets (in edge sets, out edge sets) and add degrees together. Various properties and vertex/edge index computation might be tougher.
Well, I've implemented the union_iterator, that takes 2 iterator ranges and create and unique view of them. But now I've some doubt about the union_graph adapter. Please, try to think the following questions in a Dijkstra's context: [1] Why the 2 graphs in the union_graph must have the same vertex number? Is it a vertex index issue? I think it is because when I call a function that takes a vertex_descriptor argument, I must query both the graphs on the same vertex_descriptor. Isn't it? In my initial problem I added some new vertexes on the original graph. So with the union_graph, the new vertexes in the 'little graph' aren't in the 'original graph'. I can't know a priori how much vertexes I will add in an elaboration. I must add some 'free' vertex on the original graph, to use in the elaboration? [2] When I add an edge on a graph, the graph assigns to the edge an edge_descriptor. When I add some edges to the two graphs, they can have the same edge_descriptor for different edges. So, when I call a function that takes an edge_descriptor argument, e.g. source() or target(), how can distinguish the two edge with the same edge_descriptor on two different graphs? [3] This relates to [2] directly: when I call out_edges() on a vertex, the union_graph calls out_edges() on the same vertex_descriptor in both the graphs; I obtain two ranges of edge_iterators, that I join with union_iterator adaptor, but in the two range I can find the same edge_descriptor. What do you think about? Thanks, Cosimo Calabrese.