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 10:33:27

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