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

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 > { 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 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