Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net