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