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

"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 Pgraph; // use vecS typedef adjacency_list 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