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

Subject: Re: [Boost-users] [graph] topological sort of subgraph?
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-01-16 07:30:38

>
> 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_at_[hidden]