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

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

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