Re: [Boost-users] Help on creating a custom InputIterator for boost graph adjacency_list()

Subject: Re: [Boost-users] Help on creating a custom InputIterator for boost graph adjacency_list()
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-05-24 11:00:47

On Friday, 21. May 2010 22:16:01 Jeremiah Willcock wrote:
> On Fri, 21 May 2010, Cedric Laczny wrote:
> > In fact, I was not aware that I could have the vertex_index map as a
> > member of the iterator. i only realized it recently. Unfortunately, I
> > don't program C++ that often and have never done it in such detail as I
> > have to do it now. Thus, I'm still in the process of learning and
> > especially discovering the great abilities of boost-library.
> > To answer your question, indeed, it should match. I'm thinking of
> > creating a "simple" graph as a copy of the original one, containing the
> > same number of vertices and the same edges as in the original graph
> > because I want to keep the original graph only for storing purposes.
> > More specifically, the original graph's vertices have bundled properties
> > (at the moment only 2 strings) and for the algorithm I want to
> > implement, the vertices need a mark, that can be set. First, I don't
> > know how to add this _later_ to the graph (don't even know if it is
> > possible though), and second, there might be different algorithms I have
> > to implement that will need special properties (e.g. several marks) and
> > always changing this on the original graph is not what I find that
> > "nice" :)
> 
> You can just use external properties if you want to add properties
> later; properties such as marks/colors/distances/... can just be built
> as std::vectors and turned into property maps using
> iterator_property_map.  That way, each algorithm can create its
> temporary property maps, use them, and destroy them without needing to
> copy or change the graph at all.
> 
> > Actually, I now use boost::copy_graph() to create the copy, together with
> > the following vertex copier:
> > // Used to copy only relevant properties
> > template <class G1, class G2>
> > struct Vcopier{
> > 
> >        Vcopier(const G1& g1, G2& g2)
> >        
> >                : m_g1(g1), m_g2(g2)
> >                
> >                {}
> >        
> >        // explicit cast operator
> >        // Used to "convert" one vertex into another
> >        template< class V1, class V2>
> >        void operator() (const V1& v1, const V2& v2) const
> >        {
> >        
> >                m_g2[v2] = false;
> >        
> >        }
> >        
> >        const G1& m_g1;
> >        G2& m_g2;
> > 
> > };
> > 
> > Thus, I can directly set the mark to a default value.
> > For me, as a beginner, this is far easier than doing this with a custom
> > InputIterator.
> > However, if you find that with an InputIterator this might be also nice
> > to solve, I really would appreciate an example.
> > 
> > I don't know if the vertex_index map has data in it either. However, when
> > using vecS for the vertex-list, this property_map is automatically
> > created and _not_changeable from outside (had to realize that during my
> > tests). The vertex indices are accessible via get(vertex_index, g, v)
> > and for my simple example, that numbering matches the numbering in the
> > original graph.
> > But, what I definitely need to know for sure is, if this is pure
> > coincidence or if copy_graph() does always preserve the
> > vertex-numbering?
> 
> I do not know.  Try using external properties instead of copy_graph and
> see if that solves your problem.  It should be a lot simpler and faster
> than graph copying.

Great suggestion, thank you!
This is especially apealing, as the algorithm only needs to mark the vertices 
and I don't even need the copied edges. By using external properties (here is 
a nice example 
(http://www.informit.com/articles/article.aspx?p=25777&seqNum=6))) I can also 
be sure, that the vertices stay the same and I don't risk to mix something up 
due to a probably wrong mapping from one graph to the other.
So thank you again.

> 
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

Best,

Cedric