Boost logo

Boost :

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.


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