[graph] topological sort of subgraph?
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? TIA, Emit
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?
There's not an "easy" way that I'm familiar with. You could do this: Create a color map, initializing everything to black. Run a DFS on the reverse graph with libfoobar as the root. For every vertex visited by the DFS, change its color to white. Run topological sort on the original map. This *might* do what you want. It basically disables vertices that aren't parents of the target. You'd have to see how the topological_sort algorithm actually deals with colors to be certain. Andrew Sutton andrew.n.sutton@gmail.com
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
To find the ancestors of libfoobar.a declare the graph
bidirectional, create a reversed view of the graph using the
reverse_graph adaptor, run depth_first_visit with libfoobar.a as the
starting vertex (which will only visit vertices reachable from the
starting vertex), and record the vertices reached (e.g. in a
set
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
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
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
Sorry, a small correction to my reply. the output should have been: dax.h zow.h foo.cpp foo.o yow.h boz.h bar.cpp bar.o libfoobar.a I copy and pasted the wrong line.
participants (3)
-
Andrew Sutton -
Emit Sorrels -
Michael Olea