RE: [boost] BGL: How do I find ancestors to a node?

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-01-15 10:34:55

> I see what the problem is! transitive_closure.hpp includes 
> vector_as_graph.hpp without any reasons. It should work is 
> the include is 
> commented out. To fix it permanentely, transitive_closure.w 
> need to be fixed. 

If I comment out the #include, I get almost 1000 lines of error
messages. The first is:

../boost\boost/graph/transitive_closure.hpp(116) : error C2784:
'generic-type-423 __cdecl boost::num_vertices(const class
boost::reverse_graph<BidirectionalGraph,GRef> &)' : could not deduce
template argument for 'const class boost::reverse_graph<Bi
directionalGraph,GraphRef> &' from 'class std::vector<class
std::vector<unsigned int,class std::allocator<unsigned int> >,class
std::allocator<class std::vector<unsigned int,class
std::allocator<unsigned int> > > >'
        ../boost\boost/graph/transitive_closure.hpp(248) : see reference
to function template instantiation 'void __cdecl
boost::transitive_closure(const class boost::adjacency_list<struct
boost::listS,struct boost::listS,struct boost::directedS,str
uct boost::property<enum boost::vertex_index_t,unsigned int,struct
boost::property<enum boost::vertex_name_t,class
std::basic_string<char,struct std::char_traits<char>,class
std::allocator<char> >,struct boost::property<enum
boost::edge_weight_t,int
,struct boost::property<enum boost::vertex_color_t,enum
boost::default_color_type,struct boost::no_property> > > >,struct
boost::no_property,struct boost::no_property,struct boost::listS>
&,class boost::adjacency_list<struct boost::listS,struct boos
t::listS,struct boost::directedS,struct boost::property<enum
boost::vertex_index_t,unsigned int,struct boost::property<enum
boost::vertex_name_t,class std::basic_string<char,struct
std::char_traits<char>,class std::allocator<char> >,struct boost::pr
operty<enum boost::edge_weight_t,int,struct boost::property<enum
boost::vertex_color_t,enum boost::default_color_type,struct
boost::no_property> > > >,struct boost::no_property,struct
boost::no_property,struct boost::listS> &,class boost::iterator_p
roperty_map<void * *,struct boost::adj_list_vertex_property_map<class
boost::adjacency_list<struct boost::listS,struct boost::listS,struct
boost::directedS,struct boost::property<enum
boost::vertex_index_t,unsigned int,struct boost::property<enum bo
ost::vertex_name_t,class std::basic_string<char,struct
std::char_traits<char>,class std::allocator<char> >,struct
boost::property<enum boost::edge_weight_t,int,struct
boost::property<enum boost::vertex_color_t,enum
boost::default_color_type,struct b
oost::no_property> > > >,struct boost::no_property,struct
boost::no_property,struct boost::listS>,unsigned int,unsigned int const
&,enum boost::vertex_index_t>,void *,void * &>,struct
boost::adj_list_vertex_property_map<class boost::adjacency_list<s
truct boost::listS,struct boost::listS,struct boost::dir
ctedS,struct boost::property<enum boost::vertex_index_t,unsigned
int,struct boost::property<enum boost::vertex_name_t,class
std::basic_string<char,struct std::char_traits<char>,class
std::allocator<char> >,struct boost::property<enum boost::edge_wei
ght_t,int,struct boost::property<enum boost::vertex_color_t,enum
boost::default_color_type,struct boost::no_property> > > >,struct
boost::no_property,struct boost::no_property,struct
boost::listS>,unsigned int,unsigned int const &,enum boost::vertex
_index_t>)' being compiled

This is reported on the following line in transitive_closure:

    std::vector < cg_vertex > topo_number(num_vertices(CG));

and the definition of CG is:

    typedef size_type cg_vertex;
    ...
    typedef std::vector < std::vector < cg_vertex > >CG_t;
    CG_t CG(num_scc);

If I change the num_vertices(CG) to CG.size(), I get a bit further, but
then it stops with:

../boost\boost/graph/graph_traits.hpp(38) : error C2039:
'vertex_descriptor' : is not a member of 'vector<class
std::vector<unsigned int,class std::allocator<unsigned int> >,class
std::allocator<class std::vector<unsigned int,class std::allocator<un
signed int> > > >'
        ../boost\boost/graph/transitive_closure.hpp(143) : see reference
to class template instantiation 'boost::graph_traits<class
std::vector<class std::vector<unsigned int,class std::allocator<unsigned
int> >,class std::allocator<class std::vecto
r<unsigned int,class std::allocator<unsigned int> > > > >' being
compiled

This refers to 

   typename graph_traits < CG_t >::adjacency_iterator adj_first,
adj_last;

So, it seems that you do need vector_as_graph after all?

Greets,

Asger Alstrup