[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<vertex_descriptor>). In chapter 4 of the user guide the example of finding loops in program control-flow graphs is similar. -- Michael
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 <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
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