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-19 13:08:52

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.

-- Jeremiah Willcock