Re: BGL, vertex_iterators, listS vs vecS

From: sa3h1n sa3h1n_at_[hidden])
Date: 2003-01-10 19:16:37

Thanks for the help, Paolo.

Unfortunately, I need both iterator stability which I cannot get 
with vecS and visualization capability which I cannot get with 
listS/setS.  So finally, I have settled on a quick and dirty 
solution for visualizing listS/setS graphs.  I use graphviz to write 
out the graph with addresses instead of integral vertex indices, and 
then filter graphviz output through a perl script to map 0x00146e60 -
> 0, 0x00146e78 -> 1 and so on. Not the best but it will have to do 
for now.

Unless you know of any other good graph layout/visualization package 
out there, do you ... :-)

Cheers,
S

--- In Boost-Users_at_[hidden], Paolo Fosser <pfosser_at_s...> 
wrote:
> "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