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

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-09-02 03:41:54

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<vertex_descriptor_t/*source*/, vertex_descriptor_t/*target*/>
> - 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" <tarjeik_at_[hidden]> wrote in message
> news:1062433891.31440.80.camel_at_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<vecS, vecS, undirectedS, VertexProperties,
> >                EdgeProperties>
> >
> > where Vertex/EdgeProperties are a set of defined properties.
> >