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-21 04:12:25

On Wednesday, 19. May 2010 19:08:52 Jeremiah Willcock wrote:
> On Wed, 19 May 2010, Cedric Laczny wrote:
> > Hi,
> > 
> > I have a graph with quite some information stored in its vertices and
> > edges.
> > 
> > Now I would like to perform some analyses on the general overall
> > topology of the graph. Therefore I don't need this "big graph" but only
> > a graph that has the same number of nodes and matching edges to the "big
> > graph".
> 
> Do you mean a subgraph?  There is an adaptor for those in BGL already.
> 
> > To this end, I wanted to use the adjacency_list() constructor together
> > with an EdgeIterator that models the InputIterator so the routines of
> > the boost-graph library would take care of creating the new "simple
> > graph", which indeed would be a nice solution.
> > 
> > However, I just don't get it how to program an EdgeIterator with the
> > following constraints (taken from
> > http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/adjacency_list.html):
> > 
> > The EdgeIterator must be a model of InputIterator. The value type of the
> > EdgeIterator must be a std::pair, where the type in the pair is an
> > integer type.
> 
> One thing I would recommend is to use Boost.Iterator's iterator_adaptor.
> You might even be able to do what you want with transform_iterator.
> 
> > Here's what I experimented with so far:
> > 
> > <--- Code --->
> > 
> > template< class EdgeIterator, class Edge >
> > class MyEdgeIterator// : public input_iterator< std::pair<int, int> >
> > {
> > public:
> >         MyEdgeIterator() {};
> > 
> >         MyEdgeIterator(EdgeIterator& rhs) : actual_edge_it_(rhs) {};
> > 
> >         MyEdgeIterator(const MyEdgeIterator& to_copy) {};
> > 
> >         bool operator==(const MyEdgeIterator& to_compare)
> >         {  
> >                 return actual_edge_it_ == to_compare.actual_edge_it_;
> >         }  
> > 
> >         bool operator!=(const MyEdgeIterator& to_compare)
> >         {  
> >                 return !(*this == to_compare);
> >         }  
> > 
> >         Edge operator*() const
> >         {  
> >                 return *actual_edge_it_;
> >         }
> > 
> >         const MyEdgeIterator* operator->() const;
> >         MyEdgeIterator& operator ++()
> >         {  
> >                 ++actual_edge_it_;
> >                 return *this;
> >         }  
> > 
> >         MyEdgeIterator operator ++(int)
> >         {  
> >                 MyEdgeIterator<EdgeIterator, Edge> tmp = *this;
> >                 ++*this;
> >                 return tmp;
> >         }
> > 
> > private:
> >         EdgeIterator& actual_edge_it_;
> > }
> > 
> > <--- Code-End --->
> > 
> > Especially, I'm having trouble with the fact that the EdgeIterator must
> > return a pair of the vertex indices that the actual edge "points to".
> > 
> > I think that this must include something like get(vertex_index_t,
> > adjacency_list(...), source(*EdgeIterator, adjacency_list(...)). But
> > this would mean that e.g. MyEdgeIterator would additionally need the
> > vertex-property map of vetex indices. This seems a bit too much
> > information packed into this one, small iterator.
> 
> Does the vertex numbering of the new graph need to match the numbering of
> the old one?  In any case, why can't you have the vertex_index map as a
> member of the iterator?  Property maps are supposed to be small and cheap
> to copy, and these constructors do not copy their iterators too often
> anyway.  I don't know if the vertex_index map for adjacency_list even has
> any data at all; I believe it is an identity function or something fairly
> close.  Even a fairly large iterator should not be a problem to use,
> though; if you aesthetically prefer not to store the property map, you can
> use a shared_ptr that points to the property map instead.

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" :)

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?

Thank you.

Best,

Cedric
> 
> -- Jeremiah Willcock