Re: [Boost-Users] Re: [BGL] Adding one graph to another

On Mon, 2003-09-01 at 22:33, Chris Russell wrote:

Tarjei, I do quite a bit of this sort of thing in my project. Here's what I do:

Enumerate all the vertices in the source graph. For each source vertex: - create new vertex in target graph - save new target vertex descriptor in temporary map - manually initialize target vertex properties

Enumerate all the edges in the source graph. For each source edge: - create a new edge in the target (this is where the temporary map comes into play) - manually initialize target edge properties

Nothing fancy but it works and is efficient.

Hi Chris, and thanks for the tips. This is very much along the lines I was thinking yesterday, before I decided to post here instead and do something else meanwhile :) However, I'm thinking of dropping the temporary vertex_descriptor map, as I'm using vecS to store both vertices and edges in my graph. This means that the vertex/edge descriptors are really just integer indices into vectors, so to map the vertex descriptors from the source graph to their counterparts in the target graph, I really just need to add an offset to each descriptor (which equals the number of vertices in the original graph - 1). I reckon this will be a fair bit faster than doing map indexing (maybe even a tip for yourself , changing to vecS, unless it leads to efficiency problems elsewhere).

P.S. you could stuff this algorithm into an operator+ implementation if it's aesthetically pleasing to you ;-)

:) Thought of that, but I think I'd rather stick with a method name that is more descriptive in my context ;) Thanks again! Cheers, -- Tarjei

"Tarjei Knapstad" wrote in message news:1062433891.31440.80.camel@cc-intern01...

...

On Mon, 2003-09-01 at 18:25, Tarjei Knapstad wrote:

...

I need to add/copy one graph into another, both completely connected, and then create an edge between one vertex in the original graph and a vertex in the one copied into it. The edge/vertex properties needs to be copied as well, and this needs to be fairly efficient.

The new edge is straightforward, but is there any functionality for the copy/add operation? (Something like an "add_component" algorithm I guess...) To my understanding both the copy_graph and copy_component algorithms both replace all the content in the target graph.

If not, what would be the most efficient way to solve this sort of problem?

Forgot to say that my graph type is

adjacency_list

where Vertex/EdgeProperties are a set of defined properties.