[Boost-users] Problem with BGL copy_graph algorithm - HELP

From: Tony Cook (tony__cook_at_[hidden])
Date: 2005-09-09 10:37:02

Hello,

Can anyone tell me if I've exposed a bug in the Boost Graph Library or if
the following behaviour is expected and I need to code the solution in a
different way, and if so HOW?

In summary the boost::copy_graph algorithm fails to compile when defining
the graph using std::vector for the edge container and std::list for the
vertex container (Visual Studio 7.1, Boost 1.32.0). Other graph type
definitions work. (NB I can't use the "working" graph types in my main
application as VC 7.1 bombs with an Internal Compiler Error. I'm forced to
use a vecS,lists graph just to work round the ICE problem!!). 

I've distilled the problem down to the minimum code possible.

-------------------------------------------------
// A vecS, vecS based graph works

   typedef boost::adjacency_list
      <boost::vecS, 
       boost::vecS, 
       boost::undirectedS, 
       boost::no_property,
       boost::no_property,
       boost::no_property> GoodGraphType ;

   GoodGraphType good_graph_1 ;
   GoodGraphType good_graph_2 ;
   
   boost::copy_graph (good_graph_1, good_graph_2) ; // Compiles OK

-------------------------------------------------
// A listS, vecS based graph also works

   typedef boost::adjacency_list
      <boost::listS, 
       boost::vecS,                               
       boost::undirectedS, 
       boost::no_property,
       boost::no_property,
       boost::no_property> AnotherGoodGraphType ;

   AnotherGoodGraphType another_good_graph_1 ;
   AnotherGoodGraphType another_good_graph_2 ;
   
   boost::copy_graph (another_good_graph_1, another_good_graph_2) ; //
Compiles OK

-------------------------------------------------
// A vecS, lists based graph fails to compile - BGL error or expected??  

   typedef boost::adjacency_list
      <boost::vecS, 
       boost::listS,                               // root cause of
compilation failure
       boost::undirectedS, 
       boost::no_property,
       boost::no_property,
       boost::no_property> BadGraphType ;

   BadGraphType bad_graph_1 ;
   BadGraphType bad_graph_2 ;
   
   boost::copy_graph (bad_graph_1, bad_graph_2) ; // ***** Does not compile
******

-------------------------------------------------------
Here is the exact wording of the VC7.1 compiler output. 
-------------------------------------------------------

..\boost_1_32_0\boost\property_map.hpp(349) : error C2678: binary '+' : no
operator found which takes a left-hand operand of type 'const
std::vector<_Ty>::iterator' (or there is no acceptable conversion)
        with
        [
 
_Ty=boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS,boost::vec
S,boost::undirectedS,boost::no_property,boost::no_property,boost::no_propert
y>,boost::vecS,boost::vecS,boost::undirectedS,boost::detail::retag_property_
list<boost::vertex_bundle_t,boost::no_property>::type,boost::detail::retag_p
roperty_list<boost::edge_bundle_t,boost::no_property>::type,boost::no_proper
ty,boost::listS>::config::vertex_ptr 
        ]
        ...\boost_1_32_0\boost\property_map.hpp(349) : while compiling
class-template member function 'void
boost::iterator_property_map<RandomAccessIterator,IndexMap,T,R>::operator
[](boost::iterator_property_map<RandomAccessIterator,IndexMap,T,R>::key_type
) const'
        with
        [
 
RandomAccessIterator=std::vector<boost::detail::adj_list_gen<boost::adjacenc
y_list<boost::vecS,boost::vecS,boost::undirectedS,boost::no_property,boost::
no_property,boost::no_property>,boost::vecS,boost::vecS,boost::undirectedS,b
oost::detail::retag_property_list<boost::vertex_bundle_t,boost::no_property>
::type,boost::detail::retag_property_list<boost::edge_bundle_t,boost::no_pro
perty>::type,boost::no_property,boost::listS>::config::vertex_ptr
>::iterator,
 
IndexMap=boost::property_map<boost::adjacency_list<boost::vecS,boost::listS,
boost::undirectedS,boost::no_property,boost::no_property,boost::no_property>
,boost::vertex_index_t>::const_type,
 
T=std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::ve
cS,boost::vecS,boost::undirectedS,boost::no_property,boost::no_property,boos
t::no_property>,boost::vecS,boost::vecS,boost::undirectedS,boost::detail::re
tag_property_list<boost::vertex_bundle_t,boost::no_property>::type,boost::de
tail::retag_property_list<boost::edge_bundle_t,boost::no_property>::type,boo
st::no_property,boost::listS>::config::vertex_ptr >::value_type,
 
R=std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::ve
cS,boost::vecS,boost::undirectedS,boost::no_property,boost::no_property,boos
t::no_property>,boost::vecS,boost::vecS,boost::undirectedS,boost::detail::re
tag_property_list<boost::vertex_bundle_t,boost::no_property>::type,boost::de
tail::retag_property_list<boost::edge_bundle_t,boost::no_property>::type,boo
st::no_property,boost::listS>::config::vertex_ptr >::value_type & 
        ]
        ...\boost_1_32_0\boost\graph\copy.hpp(323) : see reference to class
template instantiation
'boost::iterator_property_map<RandomAccessIterator,IndexMap,T,R>' being
compiled
        with
        [
 
RandomAccessIterator=std::vector<boost::detail::adj_list_gen<boost::adjacenc
y_list<boost::vecS,boost::vecS,boost::undirectedS,boost::no_property,boost::
no_property,boost::no_property>,boost::vecS,boost::vecS,boost::undirectedS,b
oost::detail::retag_property_list<boost::vertex_bundle_t,boost::no_property>
::type,boost::detail::retag_property_list<boost::edge_bundle_t,boost::no_pro
perty>::type,boost::no_property,boost::listS>::config::vertex_ptr
>::iterator,
 
IndexMap=boost::property_map<boost::adjacency_list<boost::vecS,boost::listS,
boost::undirectedS,boost::no_property,boost::no_property,boost::no_property>
,boost::vertex_index_t>::const_type,
 
T=std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::ve
cS,boost::vecS,boost::undirectedS,boost::no_property,boost::no_property,boos
t::no_property>,boost::vecS,boost::vecS,boost::undirectedS,boost::detail::re
tag_property_list<boost::vertex_bundle_t,boost::no_property>::type,boost::de
tail::retag_property_list<boost::edge_bundle_t,boost::no_property>::type,boo
st::no_property,boost::listS>::config::vertex_ptr >::value_type,
 
R=std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::ve
cS,boost::vecS,boost::undirectedS,boost::no_property,boost::no_property,boos
t::no_property>,boost::vecS,boost::vecS,boost::undirectedS,boost::detail::re
tag_property_list<boost::vertex_bundle_t,boost::no_property>::type,boost::de
tail::retag_property_list<boost::edge_bundle_t,boost::no_property>::type,boo
st::no_property,boost::listS>::config::vertex_ptr >::value_type & 
        ]
        ...\CopyGraphTest.cpp(50) : see reference to function template
instantiation 'void boost::copy_graph<BadGraphType,BadGraphType>(const
VertexListGraph &,MutableGraph &)' being compiled
        with
        [
            VertexListGraph=BadGraphType,
            MutableGraph=BadGraphType
        ]

-------------------------------------------------------

Here is the code from property_map.hpp the generates the error - error line
marked with //<----- HERE

 
//=========================================================================
  // Adapter to turn a RandomAccessIterator into a property map

  template <class RandomAccessIterator, 
    class IndexMap
#ifdef BOOST_NO_STD_ITERATOR_TRAITS
    , class T, class R
#else
    , class T = typename
std::iterator_traits<RandomAccessIterator>::value_type
    , class R = typename
std::iterator_traits<RandomAccessIterator>::reference
#endif
     >
  class iterator_property_map
    : public boost::put_get_helper< R, 
        iterator_property_map<RandomAccessIterator, IndexMap,
        T, R> >
  {
  public:
    typedef typename property_traits<IndexMap>::key_type key_type;
    typedef T value_type;
    typedef R reference;
    typedef boost::lvalue_property_map_tag category;

    inline iterator_property_map(
      RandomAccessIterator cc = RandomAccessIterator(), 
      const IndexMap& _id = IndexMap() ) 
      : iter(cc), index(_id) { }
    inline R operator[](key_type v) const { return *(iter + get(index, v)) ;
} //<----- HERE
  protected:
    RandomAccessIterator iter;
    IndexMap index;
  };

--------------------------------------------------------

TIA for any help in this matter

Tony Cook