[BGL] topological_sort compile error
Hi everyone, I'm having trouble with BGL's (Boost 1.33.1) topological sort. In my source code I have this simple call: std::vector<my_vertex> rev_topo_order; topological_sort(*t, std::back_inserter(rev_topo_order)); Here "t" is an iterator to a list of graphs declared like this: typedef boost::adjacency_list< boost::setS, // Out edge list type boost::listS, // Vertex list type boost::bidirectionalS, // Needed for DAG, topo sort my_property_bundle // Vertex properties > my_graph_type; The error trace below is mostly gobbledygook to me, but it looks like it's running into trouble with BGL's default bgl_named_params. The call chain runs through this curious bit of code: template <typename VertexListGraph, typename OutputIterator> void topological_sort(VertexListGraph& g, OutputIterator result) { topological_sort(g, result, bgl_named_params<int, buffer_param_t>(0)); // bogus } That looks...interesting to me. What's with the "bogus" comment? Any idea what's going on here? Any more information I can provide that would be helpful? The gmane archives show that Renaud Lepere ran into this problem in August '06 but I can't find any replies to his question. He gave a small example which I've confirmed reproduces the problem with g++ 4.1.2: #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/topological_sort.hpp> #include <iterator> typedef boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, int, int > Graph; typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; typedef std::vector< Vertex > Vertices; int main() { Graph g; Vertices vs; boost::topological_sort(g, back_inserter(vs)); } Thanks for any help you can give. -Dave ---------------------- Error trace ---------------------- ./boost-1_33_1/boost/property_map.hpp: In member function 'R boost::iterator_property_map<RandomAccessIterator, IndexMap, T, R>::operator[](typename boost::property_traits<IndexMap>::key_type) const [with RandomAccessIterator = __gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, IndexMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, T = boost::default_color_type, R = boost::default_color_type&]': ./boost-1_33_1/boost/property_map.hpp:319: instantiated from 'void boost::put(const boost::put_get_helper<Reference, PropertyMap>&, K, const V&) [with PropertyMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>, Reference = boost::default_color_type&, K = void*, V = boost::default_color_type]' ./boost-1_33_1/boost/graph/depth_first_search.hpp:197: instantiated from 'void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, ColorMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>]' ./boost-1_33_1/boost/graph/depth_first_search.hpp:246: instantiated from 'static void boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply(const VertexListGraph&, DFSVisitor, Vertex, const boost::bgl_named_params<P, T, R>&, boost::detail::error_property_not_found) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, Vertex = void*, DFSVisitor = boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, P = boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, T = boost::graph_visitor_t, R = boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property>]' ./boost-1_33_1/boost/graph/depth_first_search.hpp:324: instantiated from 'void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, P = boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, T = boost::graph_visitor_t, R = boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property>]' ./boost-1_33_1/boost/graph/topological_sort.hpp:64: instantiated from 'void boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, OutputIterator = std::back_insert_iterator<std::vector<void*, std::allocator<void*> > >, P = int, T = boost::buffer_param_t, R = boost::no_property]' ./boost-1_33_1/boost/graph/topological_sort.hpp:70: instantiated from 'void boost::topological_sort(VertexListGraph&, OutputIterator) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, OutputIterator = std::back_insert_iterator<std::vector<void*, std::allocator<void*> > >]' [ User code instantiations snipped] ./boost-1_33_1/boost/property_map.hpp:349: error: no match for 'operator+' in '((const boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>::iter + boost::get [with PropertyMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, Reference = const boost::detail::error_property_not_found&, K = void*](((const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >&)((const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >*)(&((const boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, myclass::my_property_bundle, boost::no_property, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>::index))), ((void* const&)((void* const*)(& v))))' ./lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator.h:703: note: candidates are: __gnu_cxx::__normal_iterator<_Iterator, _Container> __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+(const typename std::iterator_traits<_Iter>::difference_type&) const [with _Iterator = boost::default_color_type*, _Container = std::vector<boost::default_color_type, std::allocator<boost::default_color_type> >] ./lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:353: note: std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&) ./lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267: note: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
On 6/4/07, David A. Greene <greened@obbligato.org> wrote:
Hi everyone,
I'm having trouble with BGL's (Boost 1.33.1) topological sort. In my source code I have this simple call:
std::vector<my_vertex> rev_topo_order; topological_sort(*t, std::back_inserter(rev_topo_order));
Here "t" is an iterator to a list of graphs declared like this:
typedef boost::adjacency_list< boost::setS, // Out edge list type boost::listS, // Vertex list type boost::bidirectionalS, // Needed for DAG, topo sort my_property_bundle // Vertex properties > my_graph_type;
<snip> Hi Dave, The error you're seeing (both in your code and the example you included) is caused because the topological sort algorithm expects a vertex index map - if you don't provide one as a parameter, it uses whatever interior vertex index map the graph has. Even if you declare a vertex index map as an interior property of the graph, you still have to initialize it by mapping each vertex to an integer in the range 0..num_vertices(g)-1. See #5 in the BGL FAQ (http://www.boost.org/libs/graph/doc/faq.html) for an example of how to initialize one. Regards, Aaron
On Monday 04 June 2007 21:06, Aaron Windsor wrote:
The error you're seeing (both in your code and the example you included) is caused because the topological sort algorithm expects a vertex index map - if you don't provide one as a parameter, it uses whatever interior vertex index map the graph has. Even if you declare a vertex index map as an interior property of the graph, you still have to initialize it by mapping each vertex to an integer in the range 0..num_vertices(g)-1. See #5 in the BGL FAQ (http://www.boost.org/libs/graph/doc/faq.html) for an example of how to initialize one.
Ok, that makes sense. How do I add a vertex index map property to a graph that already has bundled properties? The FAQ example assumes property lists. Or do I need to use an external property? Thanks again for your help. -Dave
On 6/5/07, David A. Greene <greened@obbligato.org> wrote:
On Monday 04 June 2007 21:06, Aaron Windsor wrote:
The error you're seeing (both in your code and the example you included) is caused because the topological sort algorithm expects a vertex index map - if you don't provide one as a parameter, it uses whatever interior vertex index map the graph has. Even if you declare a vertex index map as an interior property of the graph, you still have to initialize it by mapping each vertex to an integer in the range 0..num_vertices(g)-1. See #5 in the BGL FAQ (http://www.boost.org/libs/graph/doc/faq.html) for an example of how to initialize one.
Ok, that makes sense.
How do I add a vertex index map property to a graph that already has bundled properties? The FAQ example assumes property lists.
Or do I need to use an external property?
Thanks again for your help.
-Dave
Hi Dave, In your example, you could just add an "index" field to the vertex_bundle structure that you're already using. Then, after initializing the index with something like: graph_traits<my_graph_type>::vertex_iterator vi, vi_end; graph_traits<my_graph_type>::vertices_size_type current_index = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) g[*vi].index = ++current_index; //g is the current graph You should be able to call the topological sort algorithm as follows (within the context you described earlier, having an iterator t over such graphs): topological_sort(*t, std::back_inserter(rev_topo_order)), vertex_index(get(&vertex_bundle::index, *t))); Regards, Aaron
participants (2)
-
Aaron Windsor -
David A. Greene