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: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-10-01 08:45:45

> 
>>> 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.