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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-10-01 18:50:52

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

Basically, yes on your first question.  Also, edges in the two graphs need 
to refer to the same vertices (or be converted).  For your last question, 
that might be a good way to do it; remember that the same single vertex 
can work for all of your unioned graphs.  If you are using numbers as 
vertex_descriptors (as in CSR and some versions of adjacency_list), you 
can have more vertices in one graph than the other as long as your 
functions always return the max vertex count; in that case, vertex numbers 
up to the min of the two graphs will be common to the two graphs.  You 
would be able to avoid an extra vertex in the original graph that way.

> [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?

See my reply to your later email about this.

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

This relates to the "overlapping edge descriptor" issue as well; see the 
other email.

-- Jeremiah Willcock