Re: [boost] Boost topological_sort attempts to advance a dereferencable iterator 20 steps outside the valid range

From: Stephen Torri (storri_at_[hidden])
Date: 2007-04-26 21:27:20

On Thu, 2007-04-26 at 11:20 -0400, Douglas Gregor wrote:
> >                 // Get list of indexes
> >                 boost::property_map<Graph_Base::Graph_t,
> >                     boost::vertex_index_t>::type ilist
> >                     = get(boost::vertex_index, m_graph);
> > 
> >                 ilist[node] = obj_ptr->get_ID();
> 
> The vertex_index property of a vertex should give each vertex a unique
> value in the range 
> 
>   [0, num_vertices(m_graph))
> 
> When the vertex_index is >= the number of vertices in the graph (which
> happens in your test program), BGL algorithms like topological_sort will
> try to access memory beyond what has been allocated for their
> properties. If you change the last line of that snippet to
> 
>                   ilist[node] = num_vertices (m_graph) - 1;
> 
> it should work fine.
> 
> The relevant part of
> http://www.boost.org/libs/graph/doc/topological_sort.html is the
> discussion of the vertex_index_map parameter.

Ok. Now that explains why my fix works. I tried to make the vertex_index
contain the unique ID that I assigned to each Component. Well that is
fine but that information is also contained in the Component. So I
switched my graph to have the following definition:

        typedef boost::property< boost::vertex_name_t,
                                 Component::ptr_t > VertexProperty_t;

        typedef boost::adjacency_list<boost::vecS, // OutEdgeList
                                      boost::vecS, // VertexList
                                      boost::directedS, // Directed
                                      VertexProperty_t> //
VertexProperties
        Graph_t;

Will each vertex_index will get a value assigned to it? I do not
understand the way the boost::property is used by the graph library.

Stephen