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

Subject: Re: [Boost-users] [graph] topological sort of subgraph?
From: Michael Olea (oleaj_at_[hidden])
Date: 2009-01-16 14:15:21

On Jan 16, 2009, at 9:41 AM, Emit Sorrels wrote:

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

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.

> 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 not sure what you mean by "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.

In the scheme above you would call, say, m_order.push_front(s) in  
your start_vertex method, where "m_order" is a member reference in  
your visitor class.

-- Michael