Re: [Boost-users] BGL - color map assertion failed

Subject: Re: [Boost-users] BGL - color map assertion failed
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-02-27 16:44:46

On Sun, 27 Feb 2011, Krisztian Sinka wrote:

> Hi,
>
> I have the following code using Boost Graph Library to use the
> breadth-first-search:
>
> -------- code start --------
>
> template<typename T>
> class MyVisitor : public boost::default_bfs_visitor{
> public:
> 	MyVisitor(T& d): boost::default_bfs_visitor(),d_(d) {};
> 	template<typename E, typename G>
> 	void tree_edge(E e,const G& g) const {
> 		typedef typename boost::graph_traits<G>::vertex_descriptor VD;
>
> 		VD u = boost::source(e,g);
> 		VD v = boost::target(e,g);
>
> 		d_[u].parent_ = v;
> 	};
> private:
> 	T& d_;
> };
> ...
> typedef boost::adjacency_list<boost::listS  // out-edges
> 							, boost::vecS    // vertex set
> 							, boost::undirectedS
> 							, boost::property<boost::vertex_name_t,IndexT>
> 							, boost::property<boost::edge_name_t,IndexT>
> 							> GraphT;
> ...
> typedef boost::graph_traits<GraphT>::vertex_descriptor	VD;
> ...
> struct DataMap {
> 	DataMap(VD p):parent_(p),distance_(0){};
> 	DataMap():parent_(0),distance_(0){};
> 	VD parent_;
> 	int distance_;
> };
> ...
> typedef std::vector<DataMap> VisitedT;
> typedef VisitedT::iterator VisitedIterT;
>
> // Graph g properly initialized here
>
> VisitedT visited(boost::num_vertices(g));
>
> for(VI i=vertices(g).first,iend=vertices(g).second;i!=iend;++i){
> 		visited[*i].parent_=*i;
> };
>
> MyVisitor<VisitedT> vis(visited);
>
> boost::breadth_first_search(g,boost::vertex(0,g),boost::visitor(vis));
>
> -------- code end --------
>
> The compiles OK, but when I run it I got:
>
> Assertion failed: (std::size_t)i < pm.n, file
> C:/boost_1_46_0/boost/graph/two_bit_color_map.hpp, line 86
>
> which is strange as I do not tweak with the color map. From the trials
> it seems that the "VisitedT" works  if it holds "simple" types like
> vertex decriptor etc and not aggregates.

That's odd.  One thing is that your own visited map is not being used by 
the breadth-first search, since you did not pass it in as the color map. 
Is that what you want -- to keep it separately?

> My intention with the DataMap to register the vertex parents and the
> vertex distance at the same time, when the edge is visited.
> Is there any limit on the library side or did I something wrong?

I don't know yet; there isn't anything in BGL that should prevent what 
you're doing.  Would it be possible to get a stack trace of the assertion 
failure, and what i and pm.n are where it fails?

-- Jeremiah Willcock