Re: [Boost-users] [BGL] topological_sort compile error

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-06-05 19:21:02

On 6/5/07, David A. Greene <greened_at_[hidden]> 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