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: Justin Leonard (justinleona_at_[hidden])
Date: 2009-07-22 14:04:09

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