Boost logo

Boost :

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 is the
discussion of the vertex_index_map parameter.

  - Doug

Boost list run by bdawes at, gregod at, cpdaniel at, john at