[Boost-users] bgl: Walking through two adjacency lists in parallel

From: Lars Kunert (lkunert_at_[hidden])
Date: 2004-09-15 02:47:24

Hi!
I am using a graph with setS as EdgeList template-parameter.

I currently try to implement to get the number of neighbors which two 
vertices have in common.
I tried to solve this problem by walking thought both out_edge_iterator - 
ranges in parallel.

        tie( i, i_end ) = out_edges( vertex_i, graph );
        tie( j, j_end ) = out_edges( vertex_j, graph );

        int a =0;
        for( ;; )
        {
            if( *i == *j ) 
            {
                ++i;
                ++j;
                ++a;
 
                if( i == iend ) return a;
                if( j == jend ) return a;
 
            } else if( *i < *j ) {     // PROBLEM
 
                ++i;
                if( i == iend ) return a;
 
            } else /* ( *i > *j ) */ {
 
                ++j;
                if( j == jend ) return a;

            };
        };

        return 0;
    };

And get the following error message:

../../../pocket_graph/src/clustering/GraphAssociation.h:147: error: no 
match 
   for 'operator<' in 'boost::iterator_facade<I, V, TC, R, D>::operator*() 

   const [with Derived = 

Which basicaly tells me that operator< is not defined for an edge 
descriptor.

After digging through some bgl-code I found the class stored_edge (in 
detail/adjacency_list.hpp )

    template <class Vertex>
    class stored_edge
      : public boost::equality_comparable1< stored_edge<Vertex>,
        boost::less_than_comparable1< stored_edge<Vertex> > >
    {
    public:
      typedef no_property property_type;
      inline stored_edge() { }
      inline stored_edge(Vertex target, const no_property& = 
no_property())
        : m_target(target) { }
      // Need to write this explicitly so stored_edge_property can
      // invoke Base::operator= (at least, for SGI MIPSPro compiler)
      inline stored_edge& operator=(const stored_edge& x) {
        m_target = x.m_target;
        return *this;
      }
      inline Vertex& get_target() const { return m_target; }
      inline const no_property& get_property() const { return s_prop; }
      inline bool operator==(const stored_edge& x) const
        { return m_target == x.get_target(); }
      inline bool operator<(const stored_edge& x) const
        { return m_target < x.get_target(); }
      //protected: need to add hash<> as a friend
      static no_property s_prop;
      // Sometimes target not used as key in the set, and in that case
      // it is ok to change the target.
      mutable Vertex m_target;
    };

for some reason I can not use operator<() or get_target(), but accessing 
m_target directly works (cause its mutable???)...

            } else if( i->m_target < j->m_target ) {  // SOLUTION ?!

However - I feel a bit uneasy to use such a low level interface... Does 
anyone know of a better solution?

Thanks for your help!

Lars