Re: [Boost-Users] BGL, vertex_iterators, listS vs vecS

From: Paolo Fosser (pfosser_at_[hidden])
Date: 2003-01-10 11:36:56

"sa3h1n " wrote:
> 
> BGL gurus:
> 
> I would like to use listS for vertex and edge lists because of
> iterator stability.
> 
> However, if I run the following code:
> 
> ------------
>     // use listS
>     typedef adjacency_list<listS, listS> Pgraph;
>     // use vecS
>     typedef adjacency_list<vecS, vecS> Pgraph2;
> 
>     int num_vertices = 2;
>     Pgraph  pg (num_vertices);
>     boost::graph_traits<Pgraph>::vertex_iterator   vi, vi_end;
>     boost::tie(vi, vi_end) = vertices(pg);
> 
>     Pgraph2 pg2 (num_vertices);
>     boost::graph_traits<Pgraph2>::vertex_iterator   vi2, vi_end2;
>     boost::tie(vi2, vi_end2) = vertices(pg2);
> 
>     for (vi, vi2; vi != vi_end && vi2 != vi_end2; vi++, vi2++)
>     {
>         std::cout << *vi  << std::endl;
>         std::cout << *vi2 << std::endl;
>     }
> ------------
> 
> I get the following output:
> 
> ------------
> 0x00146e60   <- this is *vi which uses listS
> 0            <- this is *vi2 which uses vecS
> 0x00146e78   <- this is *vi which uses listS
> 1            <- this is *vi2 which uses vecS
> ------------
> 
> One of the problems with this is when I try to display the graph
> using write_graphviz.  Vertex indices turn out be 0x0014e60 etc
> instead of nice numbers like 0, 1, etc.
> 
> Tracing execution through the debugger, it appears that vi and
> vi_end are of type generic_iterator(), whereas vi2 and vi2_end are
> of type iterator_adaptor() defined in boost/iterator_adaptors.hpp .
> Unfortunately, this is where my c++ expertise peters out.
> 
> So what is happenning here?

First of all when you dereference a vertex_iterator you get a
vertex_descriptor. You get that output because when vertexlist is listS,
vertex_descriptor happens to be a pointer (an address), whereas when
vertexlist is vecS it happens to be an integral type (don't know
precisely which, though). However you shouldn't be concerned with this
lowlevel stuff as vertex_descriptors are to be treated as handles and
thus not printed. Instead you should use a property_map (which maps a
vertex_descriptor to something else, e.g. an index).

Turning to write_graphviz, I had to use it, too. The only solution I
conceived was to use a type with vertexList=vecS when I had to serialize
(or display) graphs.

> And is there anything I can do to ensure
> iterator stability while using vecS?

Sorry, this I don't know.

> 
> Any help will be much appreciated,
> S
> 

And I hope the above will help.

--
Do you want to live forever?  Alex Chiu has invented a device which will
give you physical immortality.  Click here!
http://www.alexchiu.com/affiliates/clickthru.cgi?id=pfosser