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 12:41:26

On Fri, Jan 16, 2009 at 07:33:27AM -0800, Michael Olea wrote:
>
> On Jan 15, 2009, at 7:57 PM, Emit Sorrels wrote:
>
>> Hello,
>>
>> Using the File Dependency sample as an example,
>> if I wanted the topo sorted list of dependencies for
>> *just* libfoobar.a, is there an obvious way to do it
>> without constructing another mini graph and calling
>> topological_sort on it?
>
>
> Here's one way:
>
> 1) find the ancestors of libfoobar.a
> 2) run topological_sort on the full graph, but filter the output to  
> restrict it to ancestors
>

Well that works, but that's just as slow (actually slower)
than constructing a subgraph.
I'm looking for a one step process since a topological sort 
as implemented in this lib seems to be a dfs anyway; 
all I need is to offset the "root" vertex.

I'm looking at section 12.3.2 (DFSVisitor) in the book and 
there seems to be a "vis.start_vertex(s,g)". It sounds like
what I'm looking for but I haven't deciphered how to make use
of it in this context.

-Emit