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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-04-26 11:20:10

On Wed, 2007-04-25 at 01:07 -0500, Stephen Torri wrote:
> I am still trying to understand why boost graph's topological_sort fails
> for a test program I have made to sort five vertexes. Originally I
> compiled this program against boost 1.33.1 on a Fedora Core 6 system
> using gcc-4.1.1. After receiving no response from the boost-users list
> that could solve this problem I read the Reporting Bug document on the
> boost website.

Ah, this is an issue with the vertex index map. 

>                 // 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.

  - Doug