|
Boost Users : |
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
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net