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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-05-21 16:16:01

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.

-- Jeremiah Willcock