Re: [Boost-users] [graph] topological sort of subgraph?

Subject: Re: [Boost-users] [graph] topological sort of subgraph?
From: Emit Sorrels (emit.sorrels_at_[hidden])
Date: 2009-01-16 14:32:29

On Fri, Jan 16, 2009 at 11:15:21AM -0800, Michael Olea wrote:
> It occurred to me (while I was out) that there is no need to run  
> topological_sort on the full graph - running depth_first_visit with  
> libfoobar.a as the starting vertex (on the reversed graph) visits the  
> ancestors of libfoobar.a in reverse topological sort order. So you could 
> just stash vertex descriptors, as encountered during the dfs, in a 
> reversible container, or use "push_front" on a container that supports 
> it.
>

yes, you are exactly right. All I need to do is to ignore
topological_sort, d_f_search, and simply use d_f_visit,
which accepts as a parameter a starting "root" vertex.

the following produces exactly what I want.

reverse_graph<Graph> rg(g);
std::vector <default_color_typ> color_map(num_vertices(rg));
depth_first_vist(rg, libfoobar_a, my_visitor,
                make_iterator_property_map(color_map.begin(),
                                           get(vertex_index, rg),
                                           color_map[0]));

//output> yow.h bar.cpp zag.cpp bar.o zag.o libfoobar.a libzigzag.a killerapp                                          

where my_visitor is some visitor I define that extends dfs_visitor,
with whatever finish_vertex I want, e.g. cout<<name[u]<<" ".

Obviously this is just standard stuff, I was just wondering 
what the BGL way of doing this was (started using it yesterday).
My problem was looking at all the high level wrapper functions 
and making it harder than it really was.

I've discovered depth_first_visit, now I have to figure out what the
hairy make_iterator_property_map is doing.

thank you.

-Emit