Re: [Boost-users] [BGL] Converting between adjacency_list with listS and vecS

Subject: Re: [Boost-users] [BGL] Converting between adjacency_list with listS and vecS
From: Ethan Kim (ethkim_at_[hidden])
Date: 2009-07-22 23:12:32

Hi Justin,
Thanks for the tip / source code! I thought the library would have a
built-in copy constructor for converting between different types, but I
guess not. On another note, since this method gives an isomorphic graph, all
the properties must be copied over manually, correct? I think I'm only using
vertex_name_t which is an internal property, but.. hmm..

Thanks again!

Ethan

On Wed, Jul 22, 2009 at 2:04 PM, Justin Leonard <justinleona_at_[hidden]>wrote:

> Ethan Kim <ethkim <at> gmail.com> writes:
>
> >
> > Hi all,The long standing question I've had for BGL is how to easily
> convert a
> graph (using adjacency_list) from listS as vertex list to vecS. (And vice
> versa)
> I understand why there needs to be 2 different implementations depending on
> different uses of algorithms. But is there an easy way to convert them back
> and
> forth?Any tip would be much appreciated.Thanks,
> >
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users <at> lists.boost.org
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
> Do you mean given Graph A using listS you want to produce Graph B using
> vecS?
> How about something like this:
>
> template<class GraphFrom,class GraphTo>
> void foo(const GraphFrom& from,GraphTo& to) {
>   typedef typename GraphFrom::vertex_iterator viter;
>   typedef typename GraphFrom::vertex_descriptor vdesc;
>   typedef typename GraphFrom::edge_iterator eiter;
>   typedef std::map<viter,typename GraphTo::vertex_iterator> map_t;
>
>   map_t table;
>
>   viter vi,vend; //copy vertices
>   for(tie(vi,vend)=from.vertices(); vi!=vend; ++vi)
>      table[*vi] = add_vertex(to);
>
>   eiter ei,eend; //copy edges
>   for(tie(ei,eend)=from.edges(); ei!=eend; ++ei) {
>      vdesc s = source(*ei,from);
>      vdesc t = target(*ei,from);
>
>      add_edge(table[s],table[t]);
>   }
> }
>
> Assuming my template mangling is correct, this should produce an isomorphic
> graph of the corresponding type in about O( VlgV + ElgE ) time.
>
> Justin
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>